Google Git
Sign in
skia / external / github.com / FRIGN / libgrapheme / a17b629bb30ac9c0e3e7343449dc42085bb2fc59 / . / src / bidirectional.c
blob: 4e81df1852458c2bc18472313b3d08df2dc840ed [file] [log] [blame]
/* See LICENSE file for copyright and license details. */
#include <stdbool.h>
#include <stddef.h>
#include "../gen/bidirectional.h"
#include "../grapheme.h"
#include "util.h"
#define MAX_DEPTH 125
enum state_type {
STATE_PROP, /* in 0..23, bidi_property */
STATE_PRESERVED_PROP, /* in 0..23, preserved bidi_prop for L1-rule */
STATE_BRACKET_OFF, /* in 0..255, offset in bidi_bracket */
STATE_LEVEL, /* in 0..MAX_DEPTH+1=126, embedding level */
STATE_PARAGRAPH_LEVEL, /* in 0..1, paragraph embedding level */
STATE_VISITED, /* in 0..1, visited within isolating run */
};
static struct {
uint_least32_t filter_mask;
size_t mask_shift;
int_least16_t value_offset;
} state_lut[] = {
[STATE_PROP] = {
.filter_mask = 0x000001F, /* 00000000 00000000 00000000 00011111 */
.mask_shift = 0,
.value_offset = 0,
},
[STATE_PRESERVED_PROP] = {
.filter_mask = 0x00003E0, /* 00000000 00000000 00000011 11100000 */
.mask_shift = 5,
.value_offset = 0,
},
[STATE_BRACKET_OFF] = {
.filter_mask = 0x003FC00, /* 00000000 00000011 11111100 00000000 */
.mask_shift = 10,
.value_offset = 0,
},
[STATE_LEVEL] = {
.filter_mask = 0x1FC0000, /* 00000001 11111100 00000000 00000000 */
.mask_shift = 18,
.value_offset = -1,
},
[STATE_PARAGRAPH_LEVEL] = {
.filter_mask = 0x2000000, /* 00000010 00000000 00000000 00000000 */
.mask_shift = 25,
.value_offset = 0,
},
[STATE_VISITED] = {
.filter_mask = 0x4000000, /* 00000100 00000000 00000000 00000000 */
.mask_shift = 26,
.value_offset = 0,
},
};
static inline int_least16_t
get_state(enum state_type t, uint_least32_t input)
{
return (int_least16_t)((input & state_lut[t].filter_mask) >>
state_lut[t].mask_shift) +
state_lut[t].value_offset;
}
static inline void
set_state(enum state_type t, int_least16_t value, uint_least32_t *output)
{
*output &= ~state_lut[t].filter_mask;
*output |= ((uint_least32_t)(value - state_lut[t].value_offset)
<< state_lut[t].mask_shift) &
state_lut[t].filter_mask;
}
struct isolate_runner {
uint_least32_t *buf;
size_t buflen;
size_t start;
struct {
size_t off;
} prev, cur, next;
enum bidi_property sos, eos;
uint_least8_t paragraph_level;
int_least8_t isolating_run_level;
};
static inline enum bidi_property
ir_get_previous_prop(const struct isolate_runner *ir)
{
return (ir->prev.off == SIZE_MAX) ?
ir->sos :
(uint_least8_t)get_state(STATE_PROP,
ir->buf[ir->prev.off]);
}
static inline enum bidi_property
ir_get_current_prop(const struct isolate_runner *ir)
{
return (uint_least8_t)get_state(STATE_PROP, ir->buf[ir->cur.off]);
}
static inline enum bidi_property
ir_get_next_prop(const struct isolate_runner *ir)
{
return (ir->next.off == SIZE_MAX) ?
ir->eos :
(uint_least8_t)get_state(STATE_PROP,
ir->buf[ir->next.off]);
}
static inline enum bidi_property
ir_get_current_preserved_prop(const struct isolate_runner *ir)
{
return (uint_least8_t)get_state(STATE_PRESERVED_PROP,
ir->buf[ir->cur.off]);
}
static inline int_least8_t
ir_get_current_level(const struct isolate_runner *ir)
{
return (int_least8_t)get_state(STATE_LEVEL, ir->buf[ir->cur.off]);
}
static inline const struct bracket *
ir_get_current_bracket_prop(const struct isolate_runner *ir)
{
return bidi_bracket +
(int_least8_t)get_state(STATE_BRACKET_OFF, ir->buf[ir->cur.off]);
}
static void
ir_set_current_prop(const struct isolate_runner *ir, enum bidi_property prop)
{
set_state(STATE_PROP, (int_least16_t)prop, &(ir->buf[ir->cur.off]));
}
static void
ir_init(uint_least32_t *buf, size_t buflen, size_t off,
uint_least8_t paragraph_level, bool within, struct isolate_runner *ir)
{
size_t i;
int_least8_t sos_level;
/* initialize invariants */
ir->buf = buf;
ir->buflen = buflen;
ir->paragraph_level = paragraph_level;
ir->start = off;
/* advance off until we are at a non-removed character */
for (; off < buflen; off++) {
if (get_state(STATE_LEVEL, buf[off]) != -1) {
break;
}
}
if (off == buflen) {
/* we encountered no more non-removed character, terminate */
ir->next.off = SIZE_MAX;
return;
}
/* set the isolating run level to that of the current offset */
ir->isolating_run_level =
(int_least8_t)get_state(STATE_LEVEL, buf[off]);
/* initialize sos and eos to dummy values */
ir->sos = ir->eos = NUM_BIDI_PROPS;
/*
* we write the information of the "current" state into next,
* so that the shift-in at the first advancement moves it in
* cur, as desired.
*/
ir->next.off = off;
/*
* determine the previous state but store its offset in cur.off,
* given it's shifted in on the first advancement
*/
ir->cur.off = SIZE_MAX;
for (i = off, sos_level = -1; i >= 1; i--) {
if (get_state(STATE_LEVEL, buf[i - 1]) != -1) {
/*
* we found a character that has not been
* removed in X9
*/
sos_level = (int_least8_t)get_state(STATE_LEVEL,
buf[i - 1]);
if (within) {
/* we just take it */
ir->cur.off = i;
}
break;
}
}
if (sos_level == -1) {
/*
* there were no preceding non-removed characters, set
* sos-level to paragraph embedding level
*/
sos_level = (int_least8_t)paragraph_level;
}
if (!within || ir->cur.off == SIZE_MAX) {
/*
* we are at the beginning of the sequence; initialize
* it faithfully according to the algorithm by looking
* at the sos-level
*/
if (MAX(sos_level, ir->isolating_run_level) % 2 == 0) {
/* the higher level is even, set sos to L */
ir->sos = BIDI_PROP_L;
} else {
/* the higher level is odd, set sos to R */
ir->sos = BIDI_PROP_R;
}
}
}
static int
ir_advance(struct isolate_runner *ir)
{
enum bidi_property prop;
int_least8_t level, isolate_level, last_isolate_level;
size_t i;
if (ir->next.off == SIZE_MAX) {
/* the sequence is over */
return 1;
}
/* shift in */
ir->prev.off = ir->cur.off;
ir->cur.off = ir->next.off;
/* mark as visited */
set_state(STATE_VISITED, 1, &(ir->buf[ir->cur.off]));
/* initialize next state by going to the next character in the sequence
*/
ir->next.off = SIZE_MAX;
last_isolate_level = -1;
for (i = ir->cur.off, isolate_level = 0; i < ir->buflen; i++) {
level = (int_least8_t)get_state(STATE_LEVEL, ir->buf[i]);
prop = (uint_least8_t)get_state(STATE_PROP, ir->buf[i]);
if (level == -1) {
/* this is one of the ignored characters, skip */
continue;
} else if (level == ir->isolating_run_level) {
last_isolate_level = level;
}
/* follow BD8/BD9 and P2 to traverse the current sequence */
if (prop == BIDI_PROP_LRI || prop == BIDI_PROP_RLI ||
prop == BIDI_PROP_FSI) {
/*
* we encountered an isolate initiator, increment
* counter, but go into processing when we
* were not isolated before
*/
if (isolate_level < MAX_DEPTH) {
isolate_level++;
}
if (isolate_level != 1) {
continue;
}
} else if (prop == BIDI_PROP_PDI && isolate_level > 0) {
isolate_level--;
/*
* if the current PDI dropped the isolate-level
* to zero, it is itself part of the isolating
* run sequence; otherwise we simply continue.
*/
if (isolate_level > 0) {
continue;
}
} else if (isolate_level > 0) {
/* we are in an isolating sequence */
continue;
}
/*
* now we either still are in our sequence or we hit
* the eos-case as we left the sequence and hit the
* first non-isolating-sequence character.
*/
if (i == ir->cur.off) {
/* we were in the first initializing round */
continue;
} else if (level == ir->isolating_run_level) {
/* isolate_level-skips have been handled before, we're
* good */
/* still in the sequence */
ir->next.off = i;
} else {
/* out of sequence or isolated, compare levels via eos
*/
ir->next.off = SIZE_MAX;
if (MAX(last_isolate_level, level) % 2 == 0) {
ir->eos = BIDI_PROP_L;
} else {
ir->eos = BIDI_PROP_R;
}
}
break;
}
if (i == ir->buflen) {
/*
* the sequence ended before we could grab an offset.
* we need to determine the eos-prop by comparing the
* level of the last element in the isolating run sequence
* with the paragraph level.
*/
ir->next.off = SIZE_MAX;
if (MAX(last_isolate_level, ir->paragraph_level) % 2 == 0) {
/* the higher level is even, set eos to L */
ir->eos = BIDI_PROP_L;
} else {
/* the higher level is odd, set eos to R */
ir->eos = BIDI_PROP_R;
}
}
return 0;
}
static enum bidi_property
ir_get_last_strong_prop(const struct isolate_runner *ir)
{
struct isolate_runner tmp;
enum bidi_property last_strong_prop = ir->sos, prop;
ir_init(ir->buf, ir->buflen, ir->start, ir->paragraph_level, false,
&tmp);
for (; !ir_advance(&tmp) && tmp.cur.off < ir->cur.off;) {
prop = ir_get_current_prop(&tmp);
if (prop == BIDI_PROP_R || prop == BIDI_PROP_L ||
prop == BIDI_PROP_AL) {
last_strong_prop = prop;
}
}
return last_strong_prop;
}
static enum bidi_property
ir_get_last_strong_or_number_prop(const struct isolate_runner *ir)
{
struct isolate_runner tmp;
enum bidi_property last_strong_or_number_prop = ir->sos, prop;
ir_init(ir->buf, ir->buflen, ir->start, ir->paragraph_level, false,
&tmp);
for (; !ir_advance(&tmp) && tmp.cur.off < ir->cur.off;) {
prop = ir_get_current_prop(&tmp);
if (prop == BIDI_PROP_R || prop == BIDI_PROP_L ||
prop == BIDI_PROP_AL || prop == BIDI_PROP_EN ||
prop == BIDI_PROP_AN) {
last_strong_or_number_prop = prop;
}
}
return last_strong_or_number_prop;
}
static void
preprocess_bracket_pair(const struct isolate_runner *start,
const struct isolate_runner *end)
{
enum bidi_property prop, bracket_prop, last_strong_or_number_prop;
struct isolate_runner ir;
size_t strong_type_off;
/*
* check if the bracket contains a strong type (L or R|EN|AN)
*/
for (ir = *start, strong_type_off = SIZE_MAX,
bracket_prop = NUM_BIDI_PROPS;
!ir_advance(&ir) && ir.cur.off < end->cur.off;) {
prop = ir_get_current_prop(&ir);
if (prop == BIDI_PROP_L) {
strong_type_off = ir.cur.off;
if (ir.isolating_run_level % 2 == 0) {
/*
* set the type for both brackets to L (so they
* match the strong type they contain)
*/
bracket_prop = BIDI_PROP_L;
}
} else if (prop == BIDI_PROP_R || prop == BIDI_PROP_EN ||
prop == BIDI_PROP_AN) {
strong_type_off = ir.cur.off;
if (ir.isolating_run_level % 2 != 0) {
/*
* set the type for both brackets to R (so they
* match the strong type they contain)
*/
bracket_prop = BIDI_PROP_R;
}
}
}
if (strong_type_off == SIZE_MAX) {
/*
* there are no strong types within the brackets and we just
* leave the brackets as is
*/
return;
}
if (bracket_prop == NUM_BIDI_PROPS) {
/*
* We encountered a strong type, but it was opposite
* to the embedding direction.
* Check the previous strong type before the opening
* bracket
*/
last_strong_or_number_prop =
ir_get_last_strong_or_number_prop(start);
if (last_strong_or_number_prop == BIDI_PROP_L &&
ir.isolating_run_level % 2 != 0) {
/*
* the previous strong type is also opposite
* to the embedding direction, so the context
* was established and we set the brackets
* accordingly.
*/
bracket_prop = BIDI_PROP_L;
} else if ((last_strong_or_number_prop == BIDI_PROP_R ||
last_strong_or_number_prop == BIDI_PROP_EN ||
last_strong_or_number_prop == BIDI_PROP_AN) &&
ir.isolating_run_level % 2 == 0) {
/*
* the previous strong type is also opposite
* to the embedding direction, so the context
* was established and we set the brackets
* accordingly.
*/
bracket_prop = BIDI_PROP_R;
} else {
/* set brackets to the embedding direction */
if (ir.isolating_run_level % 2 == 0) {
bracket_prop = BIDI_PROP_L;
} else {
bracket_prop = BIDI_PROP_R;
}
}
}
ir_set_current_prop(start, bracket_prop);
ir_set_current_prop(end, bracket_prop);
/*
* any sequence of NSMs after opening or closing brackets get
* the same property as the one we set on the brackets
*/
for (ir = *start; !ir_advance(&ir) && ir_get_current_preserved_prop(
&ir) == BIDI_PROP_NSM;) {
ir_set_current_prop(&ir, bracket_prop);
}
for (ir = *end; !ir_advance(&ir) &&
ir_get_current_preserved_prop(&ir) == BIDI_PROP_NSM;) {
ir_set_current_prop(&ir, bracket_prop);
}
}
static void
preprocess_bracket_pairs(uint_least32_t *buf, size_t buflen, size_t off,
uint_least8_t paragraph_level)
{
/*
* The N0-rule deals with bracket pairs that shall be determined
* with the rule BD16. This is specified as an algorithm with a
* stack of 63 bracket openings that are used to resolve into a
* separate list of pairs, which is then to be sorted by opening
* position. Thus, even though the bracketing-depth is limited
* by 63, the algorithm, as is, requires dynamic memory
* management.
*
* A naive approach (used by Fribidi) would be to screw the
* stack-approach and simply directly determine the
* corresponding closing bracket offset for a given opening
* bracket, leading to O(n²) time complexity in the worst case
* with a lot of brackets. While many brackets are not common,
* it is still possible to find a middle ground where you obtain
* strongly linear time complexity in most common cases:
*
* Instead of a stack, we use a FIFO data structure which is
* filled with bracket openings in the order of appearance (thus
* yielding an implicit sorting!) at the top. If the
* corresponding closing bracket is encountered, it is added to
* the respective entry, making it ready to "move out" at the
* bottom (i.e. passed to the bracket processing). Due to the
* nature of the specified pair detection algorithm, which only
* cares about the bracket type and nothing else (bidi class,
* level, etc.), we can mix processing and bracket detection.
*
* Obviously, if you, for instance, have one big bracket pair at
* the bottom that has not been closed yet, it will block the
* bracket processing and the FIFO might hit its capacity limit.
* At this point, the blockage is manually resolved using the
* naive quadratic approach.
*
* To remain within the specified standard behaviour, which
* mandates that processing of brackets should stop when the
* bracketing-depth is at 63, we simply check in an "overflow"
* scenario if all 63 elements in the LIFO are unfinished, which
* corresponds with such a bracketing depth.
*/
enum bidi_property prop;
struct {
bool complete;
size_t bracket_class;
struct isolate_runner start;
struct isolate_runner end;
} fifo[63];
const struct bracket *bracket_prop, *tmp_bracket_prop;
struct isolate_runner ir, tmp_ir;
size_t fifo_len = 0, i, blevel, j, k;
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
prop = ir_get_current_prop(&ir);
bracket_prop = ir_get_current_bracket_prop(&ir);
if (prop == BIDI_PROP_ON &&
bracket_prop->type == BIDI_BRACKET_OPEN) {
if (fifo_len == LEN(fifo)) {
/*
* The FIFO is full, check first if it's
* completely blocked (i.e. no finished
* bracket pairs, triggering the standard
* that mandates to abort in such a case
*/
for (i = 0; i < fifo_len; i++) {
if (fifo[i].complete) {
break;
}
}
if (i == fifo_len) {
/* abort processing */
return;
}
/*
* by construction, the bottom entry
* in the FIFO is guaranteed to be
* unfinished (given we "consume" all
* finished bottom entries after each
* iteration).
*
* iterate, starting after the opening
* bracket, and find the corresponding
* closing bracket.
*
* if we find none, just drop the FIFO
* entry silently
*/
for (tmp_ir = fifo[0].start, blevel = 0;
!ir_advance(&tmp_ir);) {
tmp_bracket_prop =
ir_get_current_bracket_prop(
&tmp_ir);
if (tmp_bracket_prop->type ==
BIDI_BRACKET_OPEN &&
tmp_bracket_prop->class ==
bracket_prop->class) {
/* we encountered another
* opening bracket of the
* same class */
blevel++;
} else if (tmp_bracket_prop->type ==
BIDI_BRACKET_CLOSE &&
tmp_bracket_prop->class ==
bracket_prop
->class) {
/* we encountered a closing
* bracket of the same class
*/
if (blevel == 0) {
/* this is the
* corresponding
* closing bracket
*/
fifo[0].complete = true;
fifo[0].end = ir;
} else {
blevel--;
}
}
}
if (fifo[0].complete) {
/* we found the matching bracket */
preprocess_bracket_pair(
&(fifo[i].start),
&(fifo[i].end));
}
/* shift FIFO one to the left */
for (i = 1; i < fifo_len; i++) {
fifo[i - 1] = fifo[i];
}
fifo_len--;
}
/* add element to the FIFO */
fifo_len++;
fifo[fifo_len - 1].complete = false;
fifo[fifo_len - 1].bracket_class = bracket_prop->class;
fifo[fifo_len - 1].start = ir;
} else if (prop == BIDI_PROP_ON &&
bracket_prop->type == BIDI_BRACKET_CLOSE) {
/*
* go backwards in the FIFO, skip finished entries
* and simply ignore (do nothing) the closing
* bracket if we do not match anything
*/
for (i = fifo_len; i > 0; i--) {
if (bracket_prop->class ==
fifo[i - 1].bracket_class &&
!fifo[i - 1].complete) {
/* we have found a pair */
fifo[i - 1].complete = true;
fifo[i - 1].end = ir;
/* remove all uncompleted FIFO elements
* above i - 1 */
for (j = i; j < fifo_len;) {
if (fifo[j].complete) {
j++;
continue;
}
/* shift FIFO one to the left */
for (k = j + 1; k < fifo_len;
k++) {
fifo[k - 1] = fifo[k];
}
fifo_len--;
}
break;
}
}
}
/* process all ready bracket pairs from the FIFO bottom */
while (fifo_len > 0 && fifo[0].complete) {
preprocess_bracket_pair(&(fifo[0].start),
&(fifo[0].end));
/* shift FIFO one to the left */
for (j = 0; j + 1 < fifo_len; j++) {
fifo[j] = fifo[j + 1];
}
fifo_len--;
}
}
/*
* afterwards, we still might have unfinished bracket pairs
* that will remain as such, but the subsequent finished pairs
* also need to be taken into account, so we go through the
* FIFO once more and process all finished pairs
*/
for (i = 0; i < fifo_len; i++) {
if (fifo[i].complete) {
preprocess_bracket_pair(&(fifo[i].start),
&(fifo[i].end));
}
}
}
static size_t
preprocess_isolating_run_sequence(uint_least32_t *buf, size_t buflen,
size_t off, uint_least8_t paragraph_level)
{
enum bidi_property sequence_prop, prop;
struct isolate_runner ir, tmp;
size_t runsince, sequence_end;
/* W1 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (ir_get_current_prop(&ir) == BIDI_PROP_NSM) {
prop = ir_get_previous_prop(&ir);
if (prop == BIDI_PROP_LRI || prop == BIDI_PROP_RLI ||
prop == BIDI_PROP_FSI || prop == BIDI_PROP_PDI) {
ir_set_current_prop(&ir, BIDI_PROP_ON);
} else {
ir_set_current_prop(&ir, prop);
}
}
}
/* W2 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (ir_get_current_prop(&ir) == BIDI_PROP_EN &&
ir_get_last_strong_prop(&ir) == BIDI_PROP_AL) {
ir_set_current_prop(&ir, BIDI_PROP_AN);
}
}
/* W3 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (ir_get_current_prop(&ir) == BIDI_PROP_AL) {
ir_set_current_prop(&ir, BIDI_PROP_R);
}
}
/* W4 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (ir_get_previous_prop(&ir) == BIDI_PROP_EN &&
(ir_get_current_prop(&ir) == BIDI_PROP_ES ||
ir_get_current_prop(&ir) == BIDI_PROP_CS) &&
ir_get_next_prop(&ir) == BIDI_PROP_EN) {
ir_set_current_prop(&ir, BIDI_PROP_EN);
}
if (ir_get_previous_prop(&ir) == BIDI_PROP_AN &&
ir_get_current_prop(&ir) == BIDI_PROP_CS &&
ir_get_next_prop(&ir) == BIDI_PROP_AN) {
ir_set_current_prop(&ir, BIDI_PROP_AN);
}
}
/* W5 */
runsince = SIZE_MAX;
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (ir_get_current_prop(&ir) == BIDI_PROP_ET) {
if (runsince == SIZE_MAX) {
/* a new run has begun */
runsince = ir.cur.off;
}
} else if (ir_get_current_prop(&ir) == BIDI_PROP_EN) {
/* set the preceding sequence */
if (runsince != SIZE_MAX) {
ir_init(buf, buflen, runsince, paragraph_level,
(runsince > off), &tmp);
while (!ir_advance(&tmp) &&
tmp.cur.off < ir.cur.off) {
ir_set_current_prop(&tmp, BIDI_PROP_EN);
}
runsince = SIZE_MAX;
} else {
ir_init(buf, buflen, ir.cur.off,
paragraph_level, (ir.cur.off > off),
&tmp);
ir_advance(&tmp);
}
/* follow the succeeding sequence */
while (!ir_advance(&tmp)) {
if (ir_get_current_prop(&tmp) != BIDI_PROP_ET) {
break;
}
ir_set_current_prop(&tmp, BIDI_PROP_EN);
}
} else {
/* sequence ended */
runsince = SIZE_MAX;
}
}
/* W6 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
prop = ir_get_current_prop(&ir);
if (prop == BIDI_PROP_ES || prop == BIDI_PROP_ET ||
prop == BIDI_PROP_CS) {
ir_set_current_prop(&ir, BIDI_PROP_ON);
}
}
/* W7 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (ir_get_current_prop(&ir) == BIDI_PROP_EN &&
ir_get_last_strong_prop(&ir) == BIDI_PROP_L) {
ir_set_current_prop(&ir, BIDI_PROP_L);
}
}
/* N0 */
preprocess_bracket_pairs(buf, buflen, off, paragraph_level);
/* N1 */
sequence_end = SIZE_MAX;
sequence_prop = NUM_BIDI_PROPS;
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
if (sequence_end == SIZE_MAX) {
prop = ir_get_current_prop(&ir);
if (prop == BIDI_PROP_B || prop == BIDI_PROP_S ||
prop == BIDI_PROP_WS || prop == BIDI_PROP_ON ||
prop == BIDI_PROP_FSI || prop == BIDI_PROP_LRI ||
prop == BIDI_PROP_RLI || prop == BIDI_PROP_PDI) {
/* the current character is an NI (neutral
* or isolate) */
/* scan ahead to the end of the NI-sequence
*/
ir_init(buf, buflen, ir.cur.off,
paragraph_level, (ir.cur.off > off),
&tmp);
while (!ir_advance(&tmp)) {
prop = ir_get_next_prop(&tmp);
if (prop != BIDI_PROP_B &&
prop != BIDI_PROP_S &&
prop != BIDI_PROP_WS &&
prop != BIDI_PROP_ON &&
prop != BIDI_PROP_FSI &&
prop != BIDI_PROP_LRI &&
prop != BIDI_PROP_RLI &&
prop != BIDI_PROP_PDI) {
break;
}
}
/*
* check what follows and see if the text
* has the same direction on both sides
*/
if (ir_get_previous_prop(&ir) == BIDI_PROP_L &&
ir_get_next_prop(&tmp) == BIDI_PROP_L) {
sequence_end = tmp.cur.off;
sequence_prop = BIDI_PROP_L;
} else if ((ir_get_previous_prop(&ir) ==
BIDI_PROP_R ||
ir_get_previous_prop(&ir) ==
BIDI_PROP_EN ||
ir_get_previous_prop(&ir) ==
BIDI_PROP_AN) &&
(ir_get_next_prop(&tmp) ==
BIDI_PROP_R ||
ir_get_next_prop(&tmp) ==
BIDI_PROP_EN ||
ir_get_next_prop(&tmp) ==
BIDI_PROP_AN)) {
sequence_end = tmp.cur.off;
sequence_prop = BIDI_PROP_R;
}
}
}
if (sequence_end != SIZE_MAX) {
if (ir.cur.off <= sequence_end) {
ir_set_current_prop(&ir, sequence_prop);
} else {
/* end of sequence, reset */
sequence_end = SIZE_MAX;
sequence_prop = NUM_BIDI_PROPS;
}
}
}
/* N2 */
ir_init(buf, buflen, off, paragraph_level, false, &ir);
while (!ir_advance(&ir)) {
prop = ir_get_current_prop(&ir);
if (prop == BIDI_PROP_B || prop == BIDI_PROP_S ||
prop == BIDI_PROP_WS || prop == BIDI_PROP_ON ||
prop == BIDI_PROP_FSI || prop == BIDI_PROP_LRI ||
prop == BIDI_PROP_RLI || prop == BIDI_PROP_PDI) {
/* N2 */
if (ir_get_current_level(&ir) % 2 == 0) {
/* even embedding level */
ir_set_current_prop(&ir, BIDI_PROP_L);
} else {
/* odd embedding level */
ir_set_current_prop(&ir, BIDI_PROP_R);
}
}
}
return 0;
}
static uint_least8_t
get_isolated_paragraph_level(const uint_least32_t *state, size_t statelen)
{
enum bidi_property prop;
int_least8_t isolate_level;
size_t stateoff;
/* determine paragraph level (rules P1-P3) and terminate on PDI */
for (stateoff = 0, isolate_level = 0; stateoff < statelen; stateoff++) {
prop = (uint_least8_t)get_state(STATE_PROP, state[stateoff]);
if (prop == BIDI_PROP_PDI && isolate_level == 0) {
/*
* we are in a FSI-subsection of a paragraph and
* matched with the terminating PDI
*/
break;
}
/* BD8/BD9 */
if ((prop == BIDI_PROP_LRI || prop == BIDI_PROP_RLI ||
prop == BIDI_PROP_FSI) &&
isolate_level < MAX_DEPTH) {
/* we hit an isolate initiator, increment counter */
isolate_level++;
} else if (prop == BIDI_PROP_PDI && isolate_level > 0) {
isolate_level--;
}
/* P2 */
if (isolate_level > 0) {
continue;
}
/* P3 */
if (prop == BIDI_PROP_L) {
return 0;
} else if (prop == BIDI_PROP_AL || prop == BIDI_PROP_R) {
return 1;
}
}
return 0;
}
static inline uint_least8_t
get_bidi_property(uint_least32_t cp)
{
if (likely(cp <= 0x10FFFF)) {
return (bidi_minor[bidi_major[cp >> 8] + (cp & 0xff)]) &
0x1F /* 00011111 */;
} else {
return BIDI_PROP_L;
}
}
static uint_least8_t
get_paragraph_level(enum grapheme_bidirectional_direction override,
const HERODOTUS_READER *r)
{
HERODOTUS_READER tmp;
enum bidi_property prop;
int_least8_t isolate_level;
uint_least32_t cp;
/* check overrides first according to rule HL1 */
if (override == GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR) {
return 0;
} else if (override == GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL) {
return 1;
}
/* copy reader into temporary reader */
herodotus_reader_copy(r, &tmp);
/* determine paragraph level (rules P1-P3) */
for (isolate_level = 0; herodotus_read_codepoint(&tmp, true, &cp) ==
HERODOTUS_STATUS_SUCCESS;) {
prop = get_bidi_property(cp);
/* BD8/BD9 */
if ((prop == BIDI_PROP_LRI || prop == BIDI_PROP_RLI ||
prop == BIDI_PROP_FSI) &&
isolate_level < MAX_DEPTH) {
/* we hit an isolate initiator, increment counter */
isolate_level++;
} else if (prop == BIDI_PROP_PDI && isolate_level > 0) {
isolate_level--;
}
/* P2 */
if (isolate_level > 0) {
continue;
}
/* P3 */
if (prop == BIDI_PROP_L) {
return 0;
} else if (prop == BIDI_PROP_AL || prop == BIDI_PROP_R) {
return 1;
}
}
return 0;
}
static void
preprocess_paragraph(uint_least8_t paragraph_level, uint_least32_t *buf,
size_t buflen)
{
enum bidi_property prop;
int_least8_t level;
struct {
int_least8_t level;
enum grapheme_bidirectional_direction override;
bool directional_isolate;
} directional_status[MAX_DEPTH + 2], *dirstat = directional_status;
size_t overflow_isolate_count, overflow_embedding_count,
valid_isolate_count, bufoff, i, runsince;
/* X1 */
dirstat->level = (int_least8_t)paragraph_level;
dirstat->override = GRAPHEME_BIDIRECTIONAL_DIRECTION_NEUTRAL;
dirstat->directional_isolate = false;
overflow_isolate_count = overflow_embedding_count =
valid_isolate_count = 0;
for (bufoff = 0; bufoff < buflen; bufoff++) {
prop = (uint_least8_t)get_state(STATE_PROP, buf[bufoff]);
/* set paragraph level we need for line-level-processing */
set_state(STATE_PARAGRAPH_LEVEL, paragraph_level,
&(buf[bufoff]));
again:
if (prop == BIDI_PROP_RLE) {
/* X2 */
if (dirstat->level + (dirstat->level % 2 != 0) + 1 <=
MAX_DEPTH &&
overflow_isolate_count == 0 &&
overflow_embedding_count == 0) {
/* valid RLE */
dirstat++;
dirstat->level =
(dirstat - 1)->level +
((dirstat - 1)->level % 2 != 0) + 1;
dirstat->override =
GRAPHEME_BIDIRECTIONAL_DIRECTION_NEUTRAL;
dirstat->directional_isolate = false;
} else {
/* overflow RLE */
overflow_embedding_count +=
(overflow_isolate_count == 0);
}
} else if (prop == BIDI_PROP_LRE) {
/* X3 */
if (dirstat->level + (dirstat->level % 2 == 0) + 1 <=
MAX_DEPTH &&
overflow_isolate_count == 0 &&
overflow_embedding_count == 0) {
/* valid LRE */
dirstat++;
dirstat->level =
(dirstat - 1)->level +
((dirstat - 1)->level % 2 == 0) + 1;
dirstat->override =
GRAPHEME_BIDIRECTIONAL_DIRECTION_NEUTRAL;
dirstat->directional_isolate = false;
} else {
/* overflow LRE */
overflow_embedding_count +=
(overflow_isolate_count == 0);
}
} else if (prop == BIDI_PROP_RLO) {
/* X4 */
if (dirstat->level + (dirstat->level % 2 != 0) + 1 <=
MAX_DEPTH &&
overflow_isolate_count == 0 &&
overflow_embedding_count == 0) {
/* valid RLO */
dirstat++;
dirstat->level =
(dirstat - 1)->level +
((dirstat - 1)->level % 2 != 0) + 1;
dirstat->override =
GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL;
dirstat->directional_isolate = false;
} else {
/* overflow RLO */
overflow_embedding_count +=
(overflow_isolate_count == 0);
}
} else if (prop == BIDI_PROP_LRO) {
/* X5 */
if (dirstat->level + (dirstat->level % 2 == 0) + 1 <=
MAX_DEPTH &&
overflow_isolate_count == 0 &&
overflow_embedding_count == 0) {
/* valid LRE */
dirstat++;
dirstat->level =
(dirstat - 1)->level +
((dirstat - 1)->level % 2 == 0) + 1;
dirstat->override =
GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR;
dirstat->directional_isolate = false;
} else {
/* overflow LRO */
overflow_embedding_count +=
(overflow_isolate_count == 0);
}
} else if (prop == BIDI_PROP_RLI) {
/* X5a */
set_state(STATE_LEVEL, dirstat->level, &(buf[bufoff]));
if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR) {
set_state(STATE_PROP, BIDI_PROP_L,
&(buf[bufoff]));
} else if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL) {
set_state(STATE_PROP, BIDI_PROP_R,
&(buf[bufoff]));
}
if (dirstat->level + (dirstat->level % 2 != 0) + 1 <=
MAX_DEPTH &&
overflow_isolate_count == 0 &&
overflow_embedding_count == 0) {
/* valid RLI */
valid_isolate_count++;
dirstat++;
dirstat->level =
(dirstat - 1)->level +
((dirstat - 1)->level % 2 != 0) + 1;
dirstat->override =
GRAPHEME_BIDIRECTIONAL_DIRECTION_NEUTRAL;
dirstat->directional_isolate = true;
} else {
/* overflow RLI */
overflow_isolate_count++;
}
} else if (prop == BIDI_PROP_LRI) {
/* X5b */
set_state(STATE_LEVEL, dirstat->level, &(buf[bufoff]));
if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR) {
set_state(STATE_PROP, BIDI_PROP_L,
&(buf[bufoff]));
} else if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL) {
set_state(STATE_PROP, BIDI_PROP_R,
&(buf[bufoff]));
}
if (dirstat->level + (dirstat->level % 2 == 0) + 1 <=
MAX_DEPTH &&
overflow_isolate_count == 0 &&
overflow_embedding_count == 0) {
/* valid LRI */
valid_isolate_count++;
dirstat++;
dirstat->level =
(dirstat - 1)->level +
((dirstat - 1)->level % 2 == 0) + 1;
dirstat->override =
GRAPHEME_BIDIRECTIONAL_DIRECTION_NEUTRAL;
dirstat->directional_isolate = true;
} else {
/* overflow LRI */
overflow_isolate_count++;
}
} else if (prop == BIDI_PROP_FSI) {
/* X5c */
if (get_isolated_paragraph_level(
buf + (bufoff + 1),
buflen - (bufoff + 1)) == 1) {
prop = BIDI_PROP_RLI;
goto again;
} else { /* ... == 0 */
prop = BIDI_PROP_LRI;
goto again;
}
} else if (prop != BIDI_PROP_B && prop != BIDI_PROP_BN &&
prop != BIDI_PROP_PDF && prop != BIDI_PROP_PDI) {
/* X6 */
set_state(STATE_LEVEL, dirstat->level, &(buf[bufoff]));
if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR) {
set_state(STATE_PROP, BIDI_PROP_L,
&(buf[bufoff]));
} else if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL) {
set_state(STATE_PROP, BIDI_PROP_R,
&(buf[bufoff]));
}
} else if (prop == BIDI_PROP_PDI) {
/* X6a */
if (overflow_isolate_count > 0) {
/* PDI matches an overflow isolate initiator
*/
overflow_isolate_count--;
} else if (valid_isolate_count > 0) {
/* PDI matches a normal isolate initiator */
overflow_embedding_count = 0;
while (dirstat->directional_isolate == false &&
dirstat > directional_status) {
/*
* we are safe here as given the
* valid isolate count is positive
* there must be a stack-entry
* with positive directional
* isolate status, but we take
* no chances and include an
* explicit check
*
* POSSIBLE OPTIMIZATION: Whenever
* we push on the stack, check if it
* has the directional isolate
* status true and store a pointer
* to it so we can jump to it very
* quickly.
*/
dirstat--;
}
/*
* as above, the following check is not
* necessary, given we are guaranteed to
* have at least one stack entry left,
* but it's better to be safe
*/
if (dirstat > directional_status) {
dirstat--;
}
valid_isolate_count--;
}
set_state(STATE_LEVEL, dirstat->level, &(buf[bufoff]));
if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR) {
set_state(STATE_PROP, BIDI_PROP_L,
&(buf[bufoff]));
} else if (dirstat->override ==
GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL) {
set_state(STATE_PROP, BIDI_PROP_R,
&(buf[bufoff]));
}
} else if (prop == BIDI_PROP_PDF) {
/* X7 */
if (overflow_isolate_count > 0) {
/* do nothing */
} else if (overflow_embedding_count > 0) {
overflow_embedding_count--;
} else if (dirstat->directional_isolate == false &&
dirstat > directional_status) {
dirstat--;
}
} else if (prop == BIDI_PROP_B) {
/* X8 */
set_state(STATE_LEVEL, paragraph_level, &(buf[bufoff]));
}
/* X9 */
if (prop == BIDI_PROP_RLE || prop == BIDI_PROP_LRE ||
prop == BIDI_PROP_RLO || prop == BIDI_PROP_LRO ||
prop == BIDI_PROP_PDF || prop == BIDI_PROP_BN) {
set_state(STATE_LEVEL, -1, &(buf[bufoff]));
}
}
/* X10 (W1-W7, N0-N2) */
for (bufoff = 0; bufoff < buflen; bufoff++) {
if (get_state(STATE_VISITED, buf[bufoff]) == 0 &&
get_state(STATE_LEVEL, buf[bufoff]) != -1) {
bufoff += preprocess_isolating_run_sequence(
buf, buflen, bufoff, paragraph_level);
}
}
/*
* I1-I2 (given our sequential approach to processing the
* isolating run sequences, we apply this rule separately)
*/
for (bufoff = 0; bufoff < buflen; bufoff++) {
level = (int_least8_t)get_state(STATE_LEVEL, buf[bufoff]);
prop = (uint_least8_t)get_state(STATE_PROP, buf[bufoff]);
if (level % 2 == 0) {
/* even level */
if (prop == BIDI_PROP_R) {
set_state(STATE_LEVEL, level + 1,
&(buf[bufoff]));
} else if (prop == BIDI_PROP_AN ||
prop == BIDI_PROP_EN) {
set_state(STATE_LEVEL, level + 2,
&(buf[bufoff]));
}
} else {
/* odd level */
if (prop == BIDI_PROP_L || prop == BIDI_PROP_EN ||
prop == BIDI_PROP_AN) {
set_state(STATE_LEVEL, level + 1,
&(buf[bufoff]));
}
}
}
/* L1 (rules 1-3) */
runsince = SIZE_MAX;
for (bufoff = 0; bufoff < buflen; bufoff++) {
level = (int_least8_t)get_state(STATE_LEVEL, buf[bufoff]);
prop = (uint_least8_t)get_state(STATE_PRESERVED_PROP,
buf[bufoff]);
if (level == -1) {
/* ignored character */
continue;
}
/* rules 1 and 2 */
if (prop == BIDI_PROP_S || prop == BIDI_PROP_B) {
set_state(STATE_LEVEL, paragraph_level, &(buf[bufoff]));
}
/* rule 3 */
if (prop == BIDI_PROP_WS || prop == BIDI_PROP_FSI ||
prop == BIDI_PROP_LRI || prop == BIDI_PROP_RLI ||
prop == BIDI_PROP_PDI) {
if (runsince == SIZE_MAX) {
/* a new run has begun */
runsince = bufoff;
}
} else if ((prop == BIDI_PROP_S || prop == BIDI_PROP_B) &&
runsince != SIZE_MAX) {
/*
* we hit a segment or paragraph separator in a
* sequence, reset sequence-levels
*/
for (i = runsince; i < bufoff; i++) {
if (get_state(STATE_LEVEL, buf[i]) != -1) {
set_state(STATE_LEVEL, paragraph_level,
&(buf[i]));
}
}
runsince = SIZE_MAX;
} else {
/* sequence ended */
runsince = SIZE_MAX;
}
}
if (runsince != SIZE_MAX) {
/*
* this is the end of the paragraph and we
* are in a run
*/
for (i = runsince; i < buflen; i++) {
if (get_state(STATE_LEVEL, buf[i]) != -1) {
set_state(STATE_LEVEL, paragraph_level,
&(buf[i]));
}
}
runsince = SIZE_MAX;
}
}
static inline uint_least8_t
get_bidi_bracket_off(uint_least32_t cp)
{
if (likely(cp <= 0x10FFFF)) {
return (uint_least8_t)((bidi_minor[bidi_major[cp >> 8] +
(cp & 0xff)]) >>
5);
} else {
return 0;
}
}
static size_t
preprocess(HERODOTUS_READER *r, enum grapheme_bidirectional_direction override,
uint_least32_t *buf, size_t buflen,
enum grapheme_bidirectional_direction *resolved)
{
HERODOTUS_READER tmp;
size_t bufoff, bufsize, paragraph_len;
uint_least32_t cp;
uint_least8_t paragraph_level;
/* determine length and level of the paragraph */
herodotus_reader_copy(r, &tmp);
for (; herodotus_read_codepoint(&tmp, true, &cp) ==
HERODOTUS_STATUS_SUCCESS;) {
/* break on paragraph separator */
if (get_bidi_property(cp) == BIDI_PROP_B) {
break;
}
}
paragraph_len = herodotus_reader_number_read(&tmp);
paragraph_level = get_paragraph_level(override, r);
if (resolved != NULL) {
/* store resolved paragraph level in output variable */
/* TODO use enum-type */
*resolved = (paragraph_level == 0) ?
GRAPHEME_BIDIRECTIONAL_DIRECTION_LTR :
GRAPHEME_BIDIRECTIONAL_DIRECTION_RTL;
}
if (buf == NULL) {
/* see below for return value reasoning */
return paragraph_len;
}
/*
* the first step is to determine the bidirectional properties
* and store them in the buffer
*/
for (bufoff = 0;
bufoff < paragraph_len &&
herodotus_read_codepoint(r, true, &cp) == HERODOTUS_STATUS_SUCCESS;
bufoff++) {
if (bufoff < buflen) {
/*
* actually only do something when we have
* space in the level-buffer. We continue
* the iteration to be able to give a good
* return value
*/
set_state(STATE_PROP,
(uint_least8_t)get_bidi_property(cp),
&(buf[bufoff]));
set_state(STATE_BRACKET_OFF, get_bidi_bracket_off(cp),
&(buf[bufoff]));
set_state(STATE_LEVEL, 0, &(buf[bufoff]));
set_state(STATE_PARAGRAPH_LEVEL, 0, &(buf[bufoff]));
set_state(STATE_VISITED, 0, &(buf[bufoff]));
set_state(STATE_PRESERVED_PROP,
(uint_least8_t)get_bidi_property(cp),
&(buf[bufoff]));
}
}
bufsize = herodotus_reader_number_read(r);
for (bufoff = 0; bufoff < bufsize; bufoff++) {
if (get_state(STATE_PROP, buf[bufoff]) != BIDI_PROP_B &&
bufoff != bufsize - 1) {
continue;
}
/*
* we either encountered a paragraph terminator or this
* is the last character in the string.
* Call the paragraph handler on the paragraph, including
* the terminating character or last character of the
* string respectively
*/
preprocess_paragraph(paragraph_level, buf, bufoff + 1);
break;
}
/*
* we return the number of total bytes read, as the function
* should indicate if the given level-buffer is too small
*/
return herodotus_reader_number_read(r);
}
size_t
grapheme_bidirectional_preprocess_paragraph(
const uint_least32_t *src, size_t srclen,
enum grapheme_bidirectional_direction override, uint_least32_t *dest,
size_t destlen, enum grapheme_bidirectional_direction *resolved)
{
HERODOTUS_READER r;
herodotus_reader_init(&r, HERODOTUS_TYPE_CODEPOINT, src, srclen);
return preprocess(&r, override, dest, destlen, resolved);
}
static inline size_t
get_line_embedding_levels(const uint_least32_t *linedata, size_t linelen,
int_least8_t (*get_level)(const void *, size_t),
void (*set_level)(void *, size_t, int_least8_t),
void *lev, size_t levsize, bool skipignored)
{
enum bidi_property prop;
size_t i, levlen, runsince;
int_least8_t level, runlevel;
/* rule L1.4 */
runsince = SIZE_MAX;
runlevel = -1;
for (i = 0, levlen = 0; i < linelen; i++) {
level = (int_least8_t)get_state(STATE_LEVEL, linedata[i]);
prop = (uint_least8_t)get_state(STATE_PRESERVED_PROP,
linedata[i]);
/* write level into level array if we still have space */
if (level != -1 || skipignored == false) {
if (levlen <= levsize) {
set_level(lev, levlen, level);
}
levlen++;
}
if (level == -1) {
/* ignored character */
continue;
}
if (prop == BIDI_PROP_WS || prop == BIDI_PROP_FSI ||
prop == BIDI_PROP_LRI || prop == BIDI_PROP_RLI ||
prop == BIDI_PROP_PDI) {
if (runsince == SIZE_MAX) {
/* a new run has begun */
runsince = levlen - 1; /* levlen > 0 */
runlevel = (int_least8_t)get_state(
STATE_PARAGRAPH_LEVEL, linedata[i]);
}
} else {
/* sequence ended */
runsince = SIZE_MAX;
runlevel = -1;
}
}
if (runsince != SIZE_MAX) {
/*
* we hit the end of the line but were in a run;
* reset the line levels to the paragraph level
*/
for (i = runsince; i < MIN(linelen, levlen); i++) {
if (get_level(lev, i) != -1) {
set_level(lev, i, runlevel);
}
}
}
return levlen;
}
static inline int_least8_t
get_level_int8(const void *lev, size_t off)
{
return ((const int_least8_t *)lev)[off];
}
static inline void
set_level_int8(void *lev, size_t off, int_least8_t value)
{
((int_least8_t *)lev)[off] = value;
}
size_t
grapheme_bidirectional_get_line_embedding_levels(const uint_least32_t *linedata,
size_t linelen,
int_least8_t *lev,
size_t levlen)
{
return get_line_embedding_levels(linedata, linelen, get_level_int8,
set_level_int8, lev, levlen, false);
}
static inline int_least8_t
get_level_uint32(const void *lev, size_t off)
{
return (int_least8_t)((((const uint_least32_t *)lev)[off] &
UINT32_C(0x1FE00000)) >>
21) -
1;
}
static inline void
set_level_uint32(void *lev, size_t off, int_least8_t value)
{
((uint_least32_t *)lev)[off] ^=
((uint_least32_t *)lev)[off] & UINT32_C(0x1FE00000);
((uint_least32_t *)lev)[off] |= ((uint_least32_t)(value + 1)) << 21;
}
static inline int_least16_t
get_mirror_offset(uint_least32_t cp)
{
if (cp <= UINT32_C(0x10FFFF)) {
return mirror_minor[mirror_major[cp >> 8] + (cp & 0xFF)];
} else {
return 0;
}
}
size_t
grapheme_bidirectional_reorder_line(const uint_least32_t *line,
const uint_least32_t *linedata,
size_t linelen, uint_least32_t *output,
size_t outputsize)
{
size_t i, outputlen, first, last, j, k, l /*, laststart*/;
int_least8_t level, min_odd_level = MAX_DEPTH + 2, max_level = 0;
uint_least32_t tmp;
/* write output characters (and apply possible mirroring) */
for (i = 0, outputlen = 0; i < linelen; i++) {
if (get_state(STATE_LEVEL, linedata[i]) != -1) {
if (outputlen < outputsize) {
output[outputlen] =
(uint_least32_t)((int_least32_t)
line[i] +
get_mirror_offset(
line[i]));
}
outputlen++;
}
}
if (outputlen >= outputsize) {
/* clear output buffer */
for (i = 0; i < outputsize; i++) {
output[i] = GRAPHEME_INVALID_CODEPOINT;
}
/* return required size */
return outputlen;
}
/*
* write line embedding levels as metadata and codepoints into the
* output
*/
get_line_embedding_levels(linedata, linelen, get_level_uint32,
set_level_uint32, output, outputsize, true);
/* determine level range */
for (i = 0; i < outputlen; i++) {
level = get_level_uint32(output, i);
if (level == -1) {
/* ignored character */
continue;
}
if (level % 2 == 1 && level < min_odd_level) {
min_odd_level = level;
}
if (level > max_level) {
max_level = level;
}
}
for (level = max_level; level >= min_odd_level /* > 0 */; level--) {
for (i = 0; i < outputlen; i++) {
if (get_level_uint32(output, i) >= level) {
/*
* the current character has the desired level
*/
first = last = i;
/* find the end of the level-sequence */
for (i++; i < outputlen; i++) {
if (get_level_uint32(output, i) >=
level) {
/* the sequence continues */
last = i;
} else {
break;
}
}
/* invert the sequence first..last respecting
* grapheme clusters
*
* The standard only speaks of combining marks
* inversion, but we should in the perfect case
* respect _all_ grapheme clusters, which we do
* here!
*/
/* mark grapheme cluster breaks */
for (j = first; j <= last;
j += grapheme_next_character_break(
line + j, outputlen - j)) {
/*
* we use a special trick here: The
* first 21 bits of the state are filled
* with the codepoint, the next 8 bits
* are used for the level, so we can use
* the 30th bit to mark the grapheme
* cluster breaks. This allows us to
* reinvert the grapheme clusters into
* the proper direction later.
*/
output[j] |= UINT32_C(1) << 29;
}
/* global inversion */
for (k = first, l = last; k < l; k++, l--) {
/* swap */
tmp = output[k];
output[k] = output[l];
output[l] = tmp;
}
/* grapheme cluster reinversion */
#if 0
for (j = first, laststart = first; j <= last;
j++) {
if (output[j] & (UINT32_C(1) << 29)) {
/* we hit a mark! given the
* grapheme cluster is inverted,
* this means that the cluster
* ended and we now reinvert it
* again
*/
for (k = laststart, l = j;
k < l; k++, l--) {
/* swap */
tmp = output[k];
output[k] = output[l];
output[l] = tmp;
}
laststart = j + 1;
}
}
#endif
/* unmark grapheme cluster breaks */
for (j = first; j <= last; j++) {
output[j] ^= output[j] &
UINT32_C(0x20000000);
}
}
}
}
/* remove embedding level metadata */
for (i = 0; i < outputlen; i++) {
output[i] ^= output[i] & UINT32_C(0x1FE00000);
}
return outputlen;
}