...the Unicode bidi algorithm seems like a good thing to use, and more specifically I am thinking of using either the C reference implementation or the ICU implementation.
Supporting the bidi algorithm is more than a "good thing", in fact it is required - with the specific exceptions mentioned
in the rules numbered "HL" in UAX#9
However, all the bidi algorithm does is to determine the order of the elements on the display. For Hebrew, you would be nearly done at that point, but for Arabic, in particular, you still need to do shaping, that is to determine which positional variant glyph to use for which character (base on position in the word) and where to substitute ligatures (and how to place combining characters).
(That's for basic text display on a low-end device, for full text layout on a high-end publishing system, there's more).
Which implementation should I use? (for instance with respect to size, since I have limited memory,
and ease of use / ease of integration). The C implementation seems to give a pretty small footprint, which is really good.
I wouldn't be surprised if the C code ends up pretty small, and reasonably fast in comparison, but it was not particularly designed to be integrated into anything, however adapting it should be straightforward.
Do you see any issues or problems using the C reference implementation for my Arabic script rendering implementation? I guess the only work needed is to do some wrapping and additions around the core algorithm code as was described in the bidi.cpp comments.
The optimizations that were done in the C implementation by using some tables, was that with respect to size or speed (or maybe both)?
The C implementation was written as a reference implementation. However, I wanted to use tables to get to a more realistic performance than a typical reference implementation where the code follows the wording of the specification in a transparent manner. Since the Java implementation did that already, the idea was to compare the two and flush out places where the language of the spec wasn't precise enough (at the time) so that programmers following different coding strategies might end up with different interpretation of the rules. We did that and closed the loopholes, and the two versions produce identical results.
The Java reference code was never intended to be used in real code.
I believe the ICU folks took then wrote an optimized version of their own, but I know nothing about what it requires in footprint and how much of ICU you will need to drag in, in order to use it. I believe they do have some of the layout functionality I mentioned.