home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / common / ubidi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-19  |  44.3 KB  |  1,292 lines
  1. /*  
  2. *******************************************************************************
  3. *                                                                             *
  4. * COPYRIGHT:                                                                  *
  5. *   (C) Copyright International Business Machines Corporation, 1999           *
  6. *   Licensed Material - Program-Property of IBM - All Rights Reserved.        *
  7. *   US Government Users Restricted Rights - Use, duplication, or disclosure   *
  8. *   restricted by GSA ADP Schedule Contract with IBM Corp.                    *
  9. *                                                                             *
  10. *******************************************************************************
  11. *   file name:  ubidi.c
  12. *   encoding:   US-ASCII
  13. *   tab size:   8 (not used)
  14. *   indentation:4
  15. *
  16. *   created on: 1999jul27
  17. *   created by: Markus W. Scherer
  18. */
  19.  
  20. /* set import/export definitions */
  21. #ifndef U_COMMON_IMPLEMENTATION
  22. #   define U_COMMON_IMPLEMENTATION
  23. #endif
  24.  
  25. #include "cmemory.h"
  26. #include "utypes.h"
  27. #include "ustring.h"
  28. #include "uchar.h"
  29. #include "ubidi.h"
  30. #include "ubidiimp.h"
  31.  
  32. /*
  33.  * General implementation notes:
  34.  *
  35.  * Throughout the implementation, there are comments like (W2) that refer to
  36.  * rules of the BiDi algorithm in its version 5, in this example to the second
  37.  * rule of the resolution of weak types.
  38.  *
  39.  * For handling surrogate pairs, where two UChar's form one "abstract" (or UTF-32)
  40.  * character according to UTF-16, the second UChar gets the directional property of
  41.  * the entire character assigned, while the first one gets a BN, a boundary
  42.  * neutral, type, which is ignored by most of the algorithm according to
  43.  * rule (X9) and the implementation suggestions of the BiDi algorithm.
  44.  *
  45.  * Later, adjustWSLevels() will set the level for each BN to that of the
  46.  * following character (UChar), which results in surrogate pairs getting the
  47.  * same level on each of their surrogates.
  48.  *
  49.  * In a UTF-8 implementation, the same thing could be done: the last byte of
  50.  * a multi-byte sequence would get the "real" property, while all previous
  51.  * bytes of that sequence would get BN.
  52.  *
  53.  * It is not possible to assign all those parts of a character the same real
  54.  * property because this would fail in the resolution of weak types with rules
  55.  * that look at immediately surrounding types.
  56.  *
  57.  * As a related topic, this implementation does not remove Boundary Neutral
  58.  * types from the input, but ignores them whereever this is relevant.
  59.  * For example, the loop for the resolution of the weak types reads
  60.  * types until it finds a non-BN.
  61.  * Also, explicit embedding codes are neither changed into BN nor removed.
  62.  * They are only treated the same way real BNs are.
  63.  * As stated before, adjustWSLevels() takes care of them at the end.
  64.  * For the purpose of conformance, the levels of all these codes
  65.  * do not matter.
  66.  *
  67.  * Note that this implementation never modifies the dirProps
  68.  * after the initial setup.
  69.  *
  70.  *
  71.  * In this implementation, the resolution of weak types (Wn),
  72.  * neutrals (Nn), and the assignment of the resolved level (In)
  73.  * are all done in one single loop, in resolveImplicitLevels().
  74.  * Changes of dirProp values are done on the fly, without writing
  75.  * them back to the dirProps array.
  76.  *
  77.  *
  78.  * This implementation contains code that allows to bypass steps of the
  79.  * algorithm that are not needed on the specific paragraph
  80.  * in order to speed up the most common cases considerably,
  81.  * like text that is entirely LTR, or RTL text without numbers.
  82.  *
  83.  * Most of this is done by setting a bit for each directional property
  84.  * in a flags variable and later checking for whether there are
  85.  * any LTR characters or any RTL characters, or both, whether
  86.  * there are any explicit embedding codes, etc.
  87.  *
  88.  * If the (Xn) steps are performed, then the flags are re-evaluated,
  89.  * because they will then not contain the embedding codes any more
  90.  * and will be adjusted for override codes, so that subsequently
  91.  * more bypassing may be possible than what the initial flags suggested.
  92.  *
  93.  * If the text is not mixed-directional, then the
  94.  * algorithm steps for the weak type resolution are not performed,
  95.  * and all levels are set to the paragraph level.
  96.  *
  97.  * If there are no explicit embedding codes, then the (Xn) steps
  98.  * are not performed.
  99.  *
  100.  * If embedding levels are supplied as a parameter, then all
  101.  * explicit embedding codes are ignored, and the (Xn) steps
  102.  * are not performed.
  103.  *
  104.  * White Space types could get the level of the run they belong to,
  105.  * and are checked with a test of (flags&MASK_EMBEDDING) to
  106.  * consider if the paragraph direction should be considered in
  107.  * the flags variable.
  108.  *
  109.  * If there are no White Space types in the paragraph, then
  110.  * (L1) is not necessary in adjustWSLevels().
  111.  */
  112.  
  113. /* prototypes --------------------------------------------------------------- */
  114.  
  115. static void
  116. getDirProps(UBiDi *pBiDi, const UChar *text);
  117.  
  118. static UBiDiDirection
  119. resolveExplicitLevels(UBiDi *pBiDi);
  120.  
  121. static UBiDiDirection
  122. checkExplicitLevels(UBiDi *pBiDi, UErrorCode *pErrorCode);
  123.  
  124. static UBiDiDirection
  125. directionFromFlags(Flags flags);
  126.  
  127. static void
  128. resolveImplicitLevels(UBiDi *pBiDi,
  129.                       UTextOffset start, UTextOffset limit,
  130.                       DirProp sor, DirProp eor);
  131.  
  132. static void
  133. adjustWSLevels(UBiDi *pBiDi);
  134.  
  135. /* UBiDi object management -------------------------------------------------- */
  136.  
  137. U_CAPI UBiDi * U_EXPORT2
  138. ubidi_open() {
  139.     UErrorCode errorCode=U_ZERO_ERROR;
  140.     return ubidi_openSized(0, 0, &errorCode);
  141. }
  142.  
  143. U_CAPI UBiDi * U_EXPORT2
  144. ubidi_openSized(UTextOffset maxLength, UTextOffset maxRunCount, UErrorCode *pErrorCode) {
  145.     UBiDi *pBiDi;
  146.  
  147.     /* check the argument values */
  148.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  149.         return NULL;
  150.     } else if(maxLength<0 || maxRunCount<0) {
  151.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  152.         return NULL;    /* invalid arguments */
  153.     }
  154.  
  155.     /* allocate memory for the object */
  156.     pBiDi=(UBiDi *)icu_malloc(sizeof(UBiDi));
  157.     if(pBiDi==NULL) {
  158.         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  159.         return NULL;
  160.     }
  161.  
  162.     /* reset the object, all pointers NULL, all flags FALSE, all sizes 0 */
  163.     icu_memset(pBiDi, 0, sizeof(UBiDi));
  164.  
  165.     /* allocate memory for arrays as requested */
  166.     if(maxLength>0) {
  167.         if( !getInitialDirPropsMemory(pBiDi, maxLength) ||
  168.             !getInitialLevelsMemory(pBiDi, maxLength)
  169.         ) {
  170.             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  171.         }
  172.     } else {
  173.         pBiDi->mayAllocateText=TRUE;
  174.     }
  175.  
  176.     if(maxRunCount>0) {
  177.         if(maxRunCount==1) {
  178.             /* use simpleRuns[] */
  179.             pBiDi->runsSize=sizeof(Run);
  180.         } else if(!getInitialRunsMemory(pBiDi, maxRunCount)) {
  181.             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  182.         }
  183.     } else {
  184.         pBiDi->mayAllocateRuns=TRUE;
  185.     }
  186.  
  187.     if(U_SUCCESS(*pErrorCode)) {
  188.         return pBiDi;
  189.     } else {
  190.         ubidi_close(pBiDi);
  191.         return NULL;
  192.     }
  193. }
  194.  
  195. /*
  196.  * We are allowed to allocate memory if memory==NULL or
  197.  * mayAllocate==TRUE for each array that we need.
  198.  * We also try to grow and shrink memory as needed if we
  199.  * allocate it.
  200.  *
  201.  * Assume sizeNeeded>0.
  202.  * If *pMemory!=NULL, then assume *pSize>0.
  203.  *
  204.  * ### this realloc() may unnecessarily copy the old data,
  205.  * which we know we don't need any more;
  206.  * is this the best way to do this??
  207.  */
  208. extern bool_t
  209. getMemory(void **pMemory, UTextOffset *pSize, bool_t mayAllocate, UTextOffset sizeNeeded) {
  210.     /* check for existing memory */
  211.     if(*pMemory==NULL) {
  212.         /* we need to allocate memory */
  213.         if(mayAllocate && (*pMemory=icu_malloc(sizeNeeded))!=NULL) {
  214.             *pSize=sizeNeeded;
  215.             return TRUE;
  216.         } else {
  217.             return FALSE;
  218.         }
  219.     } else {
  220.         /* there is some memory, is it enough or too much? */
  221.         if(sizeNeeded>*pSize && !mayAllocate) {
  222.             /* not enough memory, and we must not allocate */
  223.             return FALSE;
  224.         } else if(sizeNeeded!=*pSize && mayAllocate) {
  225.             /* we may try to grow or shrink */
  226.             void *memory;
  227.  
  228.             if((memory=icu_realloc(*pMemory, sizeNeeded))!=NULL) {
  229.                 *pMemory=memory;
  230.                 *pSize=sizeNeeded;
  231.                 return TRUE;
  232.             } else {
  233.                 /* we failed to grow */
  234.                 return FALSE;
  235.             }
  236.         } else {
  237.             /* we have at least enough memory and must not allocate */
  238.             return TRUE;
  239.         }
  240.     }
  241. }
  242.  
  243. U_CAPI void U_EXPORT2
  244. ubidi_close(UBiDi *pBiDi) {
  245.     if(pBiDi!=NULL) {
  246.         if(pBiDi->dirPropsMemory!=NULL) {
  247.             icu_free(pBiDi->dirPropsMemory);
  248.         }
  249.         if(pBiDi->levelsMemory!=NULL) {
  250.             icu_free(pBiDi->levelsMemory);
  251.         }
  252.         if(pBiDi->runsMemory!=NULL) {
  253.             icu_free(pBiDi->runsMemory);
  254.         }
  255.         icu_free(pBiDi);
  256.     }
  257. }
  258.  
  259. /* ubidi_setPara ------------------------------------------------------------ */
  260.  
  261. U_CAPI void U_EXPORT2
  262. ubidi_setPara(UBiDi *pBiDi, const UChar *text, UTextOffset length,
  263.               UBiDiLevel paraLevel, UBiDiLevel *embeddingLevels,
  264.               UErrorCode *pErrorCode) {
  265.     UBiDiDirection direction;
  266.  
  267.     /* check the argument values */
  268.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  269.         return;
  270.     } else if(pBiDi==NULL || text==NULL ||
  271.               (UBIDI_MAX_EXPLICIT_LEVEL<paraLevel) && !IS_DEFAULT_LEVEL(paraLevel) ||
  272.               length<-1
  273.     ) {
  274.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  275.         return;
  276.     }
  277.  
  278.     if(length==-1) {
  279.         length=u_strlen(text);
  280.     }
  281.  
  282.     /* initialize the UBiDi structure */
  283.     pBiDi->length=length;
  284.     pBiDi->paraLevel=paraLevel;
  285.     pBiDi->direction=UBIDI_LTR;
  286.     pBiDi->trailingWSStart=length;  /* the levels[] will reflect the WS run */
  287.  
  288.     pBiDi->dirProps=NULL;
  289.     pBiDi->levels=NULL;
  290.     pBiDi->runs=NULL;
  291.  
  292.     if(length==0) {
  293.         /*
  294.          * For an empty paragraph, create a UBiDi object with the paraLevel and
  295.          * the flags and the direction set but without allocating zero-length arrays.
  296.          * There is nothing more to do.
  297.          */
  298.         if(IS_DEFAULT_LEVEL(paraLevel)) {
  299.             pBiDi->paraLevel&=1;
  300.         }
  301.         if(paraLevel&1) {
  302.             pBiDi->flags=DIRPROP_FLAG(R);
  303.             pBiDi->direction=UBIDI_RTL;
  304.         } else {
  305.             pBiDi->flags=DIRPROP_FLAG(L);
  306.             pBiDi->direction=UBIDI_LTR;
  307.         }
  308.  
  309.         pBiDi->runCount=0;
  310.         return;
  311.     }
  312.  
  313.     pBiDi->runCount=-1;
  314.  
  315.     /*
  316.      * Get the directional properties,
  317.      * the flags bit-set, and
  318.      * determine the partagraph level if necessary.
  319.      */
  320.     if(getDirPropsMemory(pBiDi, length)) {
  321.         pBiDi->dirProps=pBiDi->dirPropsMemory;
  322.         getDirProps(pBiDi, text);
  323.     } else {
  324.         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  325.         return;
  326.     }
  327.  
  328.     /* are explicit levels specified? */
  329.     if(embeddingLevels==NULL) {
  330.         /* no: determine explicit levels according to the (Xn) rules */\
  331.         if(getLevelsMemory(pBiDi, length)) {
  332.             pBiDi->levels=pBiDi->levelsMemory;
  333.             direction=resolveExplicitLevels(pBiDi);
  334.         } else {
  335.             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  336.             return;
  337.         }
  338.     } else {
  339.         /* set BN for all explicit codes, check that all levels are paraLevel..UBIDI_MAX_EXPLICIT_LEVEL */
  340.         pBiDi->levels=embeddingLevels;
  341.         direction=checkExplicitLevels(pBiDi, pErrorCode);
  342.         if(U_FAILURE(*pErrorCode)) {
  343.             return;
  344.         }
  345.     }
  346.  
  347.     /*
  348.      * The steps after (X9) in the UBiDi algorithm are performed only if
  349.      * the paragraph text has mixed directionality!
  350.      */
  351.     switch(direction) {
  352.     case UBIDI_LTR:
  353.         /* make sure paraLevel is even */
  354.         pBiDi->paraLevel=(pBiDi->paraLevel+1)&~1;
  355.  
  356.         /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
  357.         pBiDi->trailingWSStart=0;
  358.         break;
  359.     case UBIDI_RTL:
  360.         /* make sure paraLevel is odd */
  361.         pBiDi->paraLevel|=1;
  362.  
  363.         /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
  364.         pBiDi->trailingWSStart=0;
  365.         break;
  366.     default:
  367.         /*
  368.          * If there are no external levels specified and there
  369.          * are no significant explicit level codes in the text,
  370.          * then we can treat the entire paragraph as one run.
  371.          * Otherwise, we need to perform the following rules on runs of
  372.          * the text with the same embedding levels. (X10)
  373.          * "Significant" explicit level codes are ones that actually
  374.          * affect non-BN characters.
  375.          * Examples for "insignificant" ones are empty embeddings
  376.          * LRE-PDF, LRE-RLE-PDF-PDF, etc.
  377.          */
  378.         if(embeddingLevels==NULL && !(pBiDi->flags&DIRPROP_FLAG_MULTI_RUNS)) {
  379.             resolveImplicitLevels(pBiDi, 0, length,
  380.                                     GET_LR_FROM_LEVEL(pBiDi->paraLevel),
  381.                                     GET_LR_FROM_LEVEL(pBiDi->paraLevel));
  382.         } else {
  383.             /* sor, eor: start and end types of same-level-run */
  384.             UBiDiLevel *levels=pBiDi->levels;
  385.             UTextOffset start, limit=0;
  386.             UBiDiLevel level, nextLevel;
  387.             DirProp sor, eor;
  388.  
  389.             /* determine the first sor and set eor to it because of the loop body (sor=eor there) */
  390.             level=pBiDi->paraLevel;
  391.             nextLevel=levels[0];
  392.             if(level<nextLevel) {
  393.                 eor=GET_LR_FROM_LEVEL(nextLevel);
  394.             } else {
  395.                 eor=GET_LR_FROM_LEVEL(level);
  396.             }
  397.  
  398.             do {
  399.                 /* determine start and limit of the run (end points just behind the run) */
  400.  
  401.                 /* the values for this run's start are the same as for the previous run's end */
  402.                 sor=eor;
  403.                 start=limit;
  404.                 level=nextLevel;
  405.  
  406.                 /* search for the limit of this run */
  407.                 while(++limit<length && levels[limit]==level) {}
  408.  
  409.                 /* get the correct level of the next run */
  410.                 if(limit<length) {
  411.                     nextLevel=levels[limit];
  412.                 } else {
  413.                     nextLevel=pBiDi->paraLevel;
  414.                 }
  415.  
  416.                 /* determine eor from max(level, nextLevel); sor is last run's eor */
  417.                 if((level&~UBIDI_LEVEL_OVERRIDE)<(nextLevel&~UBIDI_LEVEL_OVERRIDE)) {
  418.                     eor=GET_LR_FROM_LEVEL(nextLevel);
  419.                 } else {
  420.                     eor=GET_LR_FROM_LEVEL(level);
  421.                 }
  422.  
  423.                 /* if the run consists of overridden directional types, then there
  424.                    are no implicit types to be resolved */
  425.                 if(!(level&UBIDI_LEVEL_OVERRIDE)) {
  426.                     resolveImplicitLevels(pBiDi, start, limit, sor, eor);
  427.                 }
  428.             } while(limit<length);
  429.         }
  430.  
  431.         /* reset the embedding levels for some non-graphic characters (L1), (X9) */
  432.         adjustWSLevels(pBiDi);
  433.         break;
  434.     }
  435.  
  436.     pBiDi->direction=direction;
  437. }
  438.  
  439. /* perform (P2)..(P3) ------------------------------------------------------- */
  440.  
  441. /*
  442.  * Get the directional properties for the text,
  443.  * calculate the flags bit-set, and
  444.  * determine the partagraph level if necessary.
  445.  */
  446. static void
  447. getDirProps(UBiDi *pBiDi, const UChar *text) {
  448.     DirProp *dirProps=pBiDi->dirPropsMemory;    /* pBiDi->dirProps is const */
  449.  
  450.     UTextOffset i=0, length=pBiDi->length;
  451.     Flags flags=0;      /* collect all directionalities in the text */
  452.     UChar uchar;
  453.     DirProp dirProp;
  454.  
  455.     if(IS_DEFAULT_LEVEL(pBiDi->paraLevel)) {
  456.         /* determine the paragraph level (P2..P3) */
  457.         for(;;) {
  458.             uchar=text[i];
  459.             if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(text[i+1])) {
  460.                 /* not a surrogate pair */
  461.                 flags|=DIRPROP_FLAG(dirProps[i]=dirProp=u_charDirection(uchar));
  462.             } else {
  463.                 /* a surrogate pair */
  464.                 dirProps[i++]=BN;   /* first surrogate in the pair gets the BN type */
  465.                 flags|=DIRPROP_FLAG(dirProps[i]=dirProp=u_charDirection(GET_UTF_32(uchar, text[i])))|DIRPROP_FLAG(BN);
  466.             }
  467.             ++i;
  468.             if(dirProp==L) {
  469.                 pBiDi->paraLevel=0;
  470.                 break;
  471.             } else if(dirProp==R || dirProp==AL) {
  472.                 pBiDi->paraLevel=1;
  473.                 break;
  474.             } else if(i==length) {
  475.                 /*
  476.                  * see comment in ubidi.h:
  477.                  * the DEFAULT_XXX values are designed so that
  478.                  * their bit 0 alone yields the intended default
  479.                  */
  480.                 pBiDi->paraLevel&=1;
  481.                 break;
  482.             }
  483.         }
  484.     }
  485.  
  486.     /* get the rest of the directional properties and the flags bits */
  487.     while(i<length) {
  488.         uchar=text[i];
  489.         if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(text[i+1])) {
  490.             /* not a surrogate pair */
  491.             flags|=DIRPROP_FLAG(dirProps[i]=u_charDirection(uchar));
  492.         } else {
  493.             /* a surrogate pair */
  494.             dirProps[i++]=BN;   /* second surrogate in the pair gets the BN type */
  495.             flags|=DIRPROP_FLAG(dirProps[i]=u_charDirection(GET_UTF_32(uchar, text[i])))|DIRPROP_FLAG(BN);
  496.         }
  497.         ++i;
  498.     }
  499.     if(flags&MASK_EMBEDDING) {
  500.         flags|=DIRPROP_FLAG_LR(pBiDi->paraLevel);
  501.     }
  502.  
  503.     pBiDi->flags=flags;
  504. }
  505.  
  506. /* perform (X1)..(X9) ------------------------------------------------------- */
  507.  
  508. /*
  509.  * Resolve the explicit levels as specified by explicit embedding codes.
  510.  * Recalculate the flags to have them reflect the real properties
  511.  * after taking the explicit embeddings into account.
  512.  *
  513.  * The BiDi algorithm is designed to result in the same behavior whether embedding
  514.  * levels are externally specified (from "styled text", supposedly the preferred
  515.  * method) or set by explicit embedding codes (LRx, RLx, PDF) in the plain text.
  516.  * That is why (X9) instructs to remove all explicit codes (and BN).
  517.  * However, in a real implementation, this removal of these codes and their index
  518.  * positions in the plain text is undesirable since it would result in
  519.  * reallocated, reindexed text.
  520.  * Instead, this implementation leaves the codes in there and just ignores them
  521.  * in the subsequent processing.
  522.  * In order to get the same reordering behavior, positions with a BN or an
  523.  * explicit embedding code just get the same level assigned as the last "real"
  524.  * character.
  525.  *
  526.  * Some implementations, not this one, then overwrite some of these
  527.  * directionality properties at "real" same-level-run boundaries by
  528.  * L or R codes so that the resolution of weak types can be performed on the
  529.  * entire paragraph at once instead of having to parse it once more and
  530.  * perform that resolution on same-level-runs.
  531.  * This limits the scope of the implicit rules in effectively
  532.  * the same way as the run limits.
  533.  *
  534.  * Instead, this implementation does not modify these codes.
  535.  * On one hand, the paragraph has to be scanned for same-level-runs, but
  536.  * on the other hand, this saves another loop to reset these codes,
  537.  * or saves making and modifying a copy of dirProps[].
  538.  *
  539.  *
  540.  * Note that (Pn) and (Xn) changed significantly from version 4 of the BiDi algorithm.
  541.  *
  542.  *
  543.  * Handling the stack of explicit levels (Xn):
  544.  *
  545.  * With the BiDi stack of explicit levels,
  546.  * as pushed with each LRE, RLE, LRO, and RLO and popped with each PDF,
  547.  * the explicit level must never exceed UBIDI_MAX_EXPLICIT_LEVEL==61.
  548.  *
  549.  * In order to have a correct push-pop semantics even in the case of overflows,
  550.  * there are two overflow counters:
  551.  * - countOver60 is incremented with each LRx at level 60
  552.  * - from level 60, one RLx increases the level to 61
  553.  * - countOver61 is incremented with each LRx and RLx at level 61
  554.  *
  555.  * Popping levels with PDF must work in the opposite order so that level 61
  556.  * is correct at the correct point. Underflows (too many PDFs) must be checked.
  557.  *
  558.  * This implementation assumes that UBIDI_MAX_EXPLICIT_LEVEL is odd.
  559.  */
  560.  
  561. static UBiDiDirection
  562. resolveExplicitLevels(UBiDi *pBiDi) {
  563.     const DirProp *dirProps=pBiDi->dirProps;
  564.     UBiDiLevel *levels=pBiDi->levels;
  565.     
  566.     UTextOffset i=0, length=pBiDi->length;
  567.     Flags flags=pBiDi->flags;       /* collect all directionalities in the text */
  568.     DirProp dirProp;
  569.     UBiDiLevel level=pBiDi->paraLevel;
  570.  
  571.     UBiDiDirection direction;
  572.  
  573.     /* determine if the text is mixed-directional or single-directional */
  574.     direction=directionFromFlags(flags);
  575.  
  576.     /* we may not need to resolve any explicit levels */
  577.     if(direction!=UBIDI_MIXED) {
  578.         /* not mixed directionality: levels don't matter - trailingWSStart will be 0 */
  579.     } else if(!(flags&MASK_EXPLICIT)) {
  580.         /* mixed, but all characters are at the same embedding level */
  581.         /* set all levels to the paragraph level */
  582.         for(i=0; i<length; ++i) {
  583.             levels[i]=level;
  584.         }
  585.     } else {
  586.         /* continue to perform (Xn) */
  587.  
  588.         /* (X1) level is set for all codes, embeddingLevel keeps track of the push/pop operations */
  589.         /* both variables may carry the UBIDI_LEVEL_OVERRIDE flag to indicate the override status */
  590.         UBiDiLevel embeddingLevel=level, newLevel, stackTop=0;
  591.  
  592.         UBiDiLevel stack[UBIDI_MAX_EXPLICIT_LEVEL];        /* we never push anything >=UBIDI_MAX_EXPLICIT_LEVEL */
  593.         uint32_t countOver60=0, countOver61=0;  /* count overflows of explicit levels */
  594.  
  595.         /* recalculate the flags */
  596.         flags=0;
  597.  
  598.         /* since we assume that this is a single paragraph, we ignore (X8) */
  599.         for(i=0; i<length; ++i) {
  600.             dirProp=dirProps[i];
  601.             switch(dirProp) {
  602.             case LRE:
  603.             case LRO:
  604.                 /* (X3, X5) */
  605.                 newLevel=(embeddingLevel+2)&~(UBIDI_LEVEL_OVERRIDE|1);    /* least greater even level */
  606.                 if(newLevel<=UBIDI_MAX_EXPLICIT_LEVEL) {
  607.                     stack[stackTop]=embeddingLevel;
  608.                     ++stackTop;
  609.                     embeddingLevel=newLevel;
  610.                     if(dirProp==LRO) {
  611.                         embeddingLevel|=UBIDI_LEVEL_OVERRIDE;
  612.                     } else {
  613.                         embeddingLevel&=~UBIDI_LEVEL_OVERRIDE;
  614.                     }
  615.                 } else if((embeddingLevel&~UBIDI_LEVEL_OVERRIDE)==UBIDI_MAX_EXPLICIT_LEVEL) {
  616.                     ++countOver61;
  617.                 } else /* (embeddingLevel&~UBIDI_LEVEL_OVERRIDE)==UBIDI_MAX_EXPLICIT_LEVEL-1 */ {
  618.                     ++countOver60;
  619.                 }
  620.                 flags|=DIRPROP_FLAG(BN);
  621.                 break;
  622.             case RLE:
  623.             case RLO:
  624.                 /* (X2, X4) */
  625.                 newLevel=((embeddingLevel&~UBIDI_LEVEL_OVERRIDE)+1)|1;    /* least greater odd level */
  626.                 if(newLevel<=UBIDI_MAX_EXPLICIT_LEVEL) {
  627.                     stack[stackTop]=embeddingLevel;
  628.                     ++stackTop;
  629.                     embeddingLevel=newLevel;
  630.                     if(dirProp==RLO) {
  631.                         embeddingLevel|=UBIDI_LEVEL_OVERRIDE;
  632.                     } else {
  633.                         embeddingLevel&=~UBIDI_LEVEL_OVERRIDE;
  634.                     }
  635.                 } else {
  636.                     ++countOver61;
  637.                 }
  638.                 flags|=DIRPROP_FLAG(BN);
  639.                 break;
  640.             case PDF:
  641.                 /* (X7) */
  642.                 /* handle all the overflow cases first */
  643.                 if(countOver61>0) {
  644.                     --countOver61;
  645.                 } else if(countOver60>0 && (embeddingLevel&~UBIDI_LEVEL_OVERRIDE)!=UBIDI_MAX_EXPLICIT_LEVEL) {
  646.                     /* handle LRx overflows from level 60 */
  647.                     --countOver60;
  648.                 } else if(stackTop>0) {
  649.                     /* this is the pop operation; it also pops level 61 while countOver60>0 */
  650.                     --stackTop;
  651.                     embeddingLevel=stack[stackTop];
  652.                 /* } else { (underflow) */
  653.                 }
  654.                 flags|=DIRPROP_FLAG(BN);
  655.                 break;
  656.             case B:
  657.                 /*
  658.                  * We do not really expect to see a paragraph separator (B),
  659.                  * but we should do something reasonable with it,
  660.                  * especially at the end of the text.
  661.                  */
  662.                 stackTop=0;
  663.                 countOver60=countOver61=0;
  664.                 embeddingLevel=level=pBiDi->paraLevel;
  665.                 flags|=DIRPROP_FLAG(B);
  666.                 break;
  667.             case BN:
  668.                 /* BN, LRE, RLE, and PDF are supposed to be removed (X9) */
  669.                 /* they will get their levels set correctly in adjustWSLevels() */
  670.                 flags|=DIRPROP_FLAG(BN);
  671.                 break;
  672.             default:
  673.                 /* all other types get the "real" level */
  674.                 if(level!=embeddingLevel) {
  675.                     level=embeddingLevel;
  676.                     if(level&UBIDI_LEVEL_OVERRIDE) {
  677.                         flags|=DIRPROP_FLAG_O(level)|DIRPROP_FLAG_MULTI_RUNS;
  678.                     } else {
  679.                         flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG_MULTI_RUNS;
  680.                     }
  681.                 }
  682.                 if(!(level&UBIDI_LEVEL_OVERRIDE)) {
  683.                     flags|=DIRPROP_FLAG(dirProp);
  684.                 }
  685.                 break;
  686.             }
  687.  
  688.             /*
  689.              * We need to set reasonable levels even on BN codes and
  690.              * explicit codes because we will later look at same-level runs (X10).
  691.              */
  692.             levels[i]=level;
  693.         }
  694.         if(flags&MASK_EMBEDDING) {
  695.             flags|=DIRPROP_FLAG_LR(pBiDi->paraLevel);
  696.         }
  697.  
  698.         /* subsequently, ignore the explicit codes and BN (X9) */
  699.  
  700.         /* again, determine if the text is mixed-directional or single-directional */
  701.         pBiDi->flags=flags;
  702.         direction=directionFromFlags(flags);
  703.     }
  704.     return direction;
  705. }
  706.  
  707. /*
  708.  * Use a pre-specified embedding levels array:
  709.  *
  710.  * Adjust the directional properties for overrides (->LEVEL_OVERRIDE),
  711.  * ignore all explicit codes (X9),
  712.  * and check all the preset levels.
  713.  *
  714.  * Recalculate the flags to have them reflect the real properties
  715.  * after taking the explicit embeddings into account.
  716.  */
  717. static UBiDiDirection
  718. checkExplicitLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
  719.     const DirProp *dirProps=pBiDi->dirProps;
  720.     UBiDiLevel *levels=pBiDi->levels;
  721.     
  722.     UTextOffset i, length=pBiDi->length;
  723.     Flags flags=0;  /* collect all directionalities in the text */
  724.     UBiDiLevel level, paraLevel=pBiDi->paraLevel;
  725.  
  726.     for(i=0; i<length; ++i) {
  727.         level=levels[i];
  728.         if(level&UBIDI_LEVEL_OVERRIDE) {
  729.             /* keep the override flag in levels[i] but adjust the flags */
  730.             level&=~UBIDI_LEVEL_OVERRIDE;     /* make the range check below simpler */
  731.             flags|=DIRPROP_FLAG_O(level);
  732.         } else {
  733.             /* set the flags */
  734.             flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG(dirProps[i]);
  735.         }
  736.         if(level<paraLevel || UBIDI_MAX_EXPLICIT_LEVEL<level) {
  737.             /* level out of bounds */
  738.             *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  739.             return UBIDI_LTR;
  740.         }
  741.     }
  742.     if(flags&MASK_EMBEDDING) {
  743.         flags|=DIRPROP_FLAG_LR(pBiDi->paraLevel);
  744.     }
  745.  
  746.     /* determine if the text is mixed-directional or single-directional */
  747.     pBiDi->flags=flags;
  748.     return directionFromFlags(flags);
  749. }
  750.  
  751. /* determine if the text is mixed-directional or single-directional */
  752. static UBiDiDirection
  753. directionFromFlags(Flags flags) {
  754.     /* if the text contains AN and neutrals, then some neutrals may become RTL */
  755.     if(!(flags&MASK_RTL || flags&DIRPROP_FLAG(AN) && flags&MASK_POSSIBLE_N)) {
  756.         return UBIDI_LTR;
  757.     } else if(!(flags&MASK_LTR)) {
  758.         return UBIDI_RTL;
  759.     } else {
  760.         return UBIDI_MIXED;
  761.     }
  762. }
  763.  
  764. /* perform rules (Wn), (Nn), and (In) on a run of the text ------------------ */
  765.  
  766. /*
  767.  * This implementation of the (Wn) rules applies all rules in one pass.
  768.  * In order to do so, it needs a look-ahead of typically 1 character
  769.  * (except for W5: sequences of ET) and keeps track of changes
  770.  * in a rule Wp that affect a later Wq (p<q).
  771.  *
  772.  * historyOfEN is a variable-saver: it contains 4 boolean states;
  773.  * a bit in it set to 1 means:
  774.  *  bit 0: the current code is an EN after W2
  775.  *  bit 1: the current code is an EN after W4
  776.  *  bit 2: the previous code was an EN after W2
  777.  *  bit 3: the previous code was an EN after W4
  778.  * In other words, b0..1 have transitions of EN in the current iteration,
  779.  * while b2..3 have the transitions of EN in the previous iteration.
  780.  * A simple historyOfEN<<=2 suffices for the propagation.
  781.  *
  782.  * The (Nn) and (In) rules are also performed in that same single loop,
  783.  * but effectively one iteration behind for white space.
  784.  *
  785.  * Since all implicit rules are performed in one step, it is not necessary
  786.  * to actually store the intermediate directional properties in dirProps[].
  787.  */
  788.  
  789. #define EN_SHIFT 2
  790. #define EN_AFTER_W2 1
  791. #define EN_AFTER_W4 2
  792. #define EN_ALL 3
  793. #define PREV_EN_AFTER_W2 4
  794. #define PREV_EN_AFTER_W4 8
  795.  
  796. static void
  797. resolveImplicitLevels(UBiDi *pBiDi,
  798.                       UTextOffset start, UTextOffset limit,
  799.                       DirProp sor, DirProp eor) {
  800.     const DirProp *dirProps=pBiDi->dirProps;
  801.     UBiDiLevel *levels=pBiDi->levels;
  802.  
  803.     UTextOffset i, next, neutralStart=-1;
  804.     DirProp prevDirProp, dirProp, nextDirProp, lastStrong, beforeNeutral;
  805.     uint8_t historyOfEN;
  806.  
  807.     /* initialize: current at sor, next at start (it is start<limit) */
  808.     next=start;
  809.     dirProp=lastStrong=sor;
  810.     nextDirProp=dirProps[next];
  811.     historyOfEN=0;
  812.  
  813.     /*
  814.      * In all steps of this implementation, BN and explicit embedding codes
  815.      * must be treated as if they didn't exist (X9).
  816.      * They will get levels set before a non-neutral character, and remain
  817.      * undefined before a neutral one, but adjustWSLevels() will take care
  818.      * of all of them.
  819.      */
  820.     while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT) {
  821.         if(++next<limit) {
  822.             nextDirProp=dirProps[next];
  823.         } else {
  824.             nextDirProp=eor;
  825.             break;
  826.         }
  827.     }
  828.  
  829.     /*
  830.      * Note: at the end of this file, there is a prototype
  831.      * of a version of this function that uses a statetable
  832.      * at the core of this state machine.
  833.      * If you make changes to this state machine,
  834.      * please update that prototype as well.
  835.      */
  836.  
  837.     /* loop for entire run */
  838.     while(next<limit) {
  839.         /* advance */
  840.         prevDirProp=dirProp;
  841.         dirProp=nextDirProp;
  842.         i=next;
  843.         do {
  844.             if(++next<limit) {
  845.                 nextDirProp=dirProps[next];
  846.             } else {
  847.                 nextDirProp=eor;
  848.                 break;
  849.             }
  850.         } while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT);
  851.         historyOfEN<<=EN_SHIFT;
  852.  
  853.         /* (W1..W7) */
  854.         switch(dirProp) {
  855.         case L:
  856.             lastStrong=L;
  857.             break;
  858.         case R:
  859.             lastStrong=R;
  860.             break;
  861.         case AL:
  862.             /* (W3) */
  863.             lastStrong=AL;
  864.             dirProp=R;
  865.             break;
  866.         case EN:
  867.             /* we have to set historyOfEN correctly */
  868.             if(lastStrong==AL) {
  869.                 /* (W2) */
  870.                 dirProp=AN;
  871.             } else {
  872.                 if(lastStrong==L) {
  873.                     /* (W7) */
  874.                     dirProp=L;
  875.                 }
  876.                 /* this EN stays after (W2) and (W4) - at least before (W7) */
  877.                 historyOfEN|=EN_ALL;
  878.             }
  879.             break;
  880.         case ES:
  881.             if( historyOfEN&PREV_EN_AFTER_W2 &&     /* previous was EN before (W4) */
  882.                 nextDirProp==EN && lastStrong!=AL   /* next is EN and (W2) won't make it AN */
  883.             ) {
  884.                 /* (W4) */
  885.                 if(lastStrong!=L) {
  886.                     dirProp=EN;
  887.                 } else {
  888.                     /* (W7) */
  889.                     dirProp=L;
  890.                 }
  891.                 historyOfEN|=EN_AFTER_W4;
  892.             } else {
  893.                 /* (W6) */
  894.                 dirProp=ON;
  895.             }
  896.             break;
  897.         case CS:
  898.             if( historyOfEN&PREV_EN_AFTER_W2 &&     /* previous was EN before (W4) */
  899.                 nextDirProp==EN && lastStrong!=AL   /* next is EN and (W2) won't make it AN */
  900.             ) {
  901.                 /* (W4) */
  902.                 if(lastStrong!=L) {
  903.                     dirProp=EN;
  904.                 } else {
  905.                     /* (W7) */
  906.                     dirProp=L;
  907.                 }
  908.                 historyOfEN|=EN_AFTER_W4;
  909.             } else if(prevDirProp==AN &&                    /* previous was AN */
  910.                       (nextDirProp==AN ||                   /* next is AN */
  911.                        nextDirProp==EN && lastStrong==AL)   /* or (W2) will make it one */
  912.             ) {
  913.                 /* (W4) */
  914.                 dirProp=AN;
  915.             } else {
  916.                 /* (W6) */
  917.                 dirProp=ON;
  918.             }
  919.             break;
  920.         case ET:
  921.             /* get sequence of ET; advance only next, not current, previous or historyOfEN */
  922.             while(next<limit && DIRPROP_FLAG(nextDirProp)&MASK_ET_NSM_BN /* (W1), (X9) */) {
  923.                 if(++next<limit) {
  924.                     nextDirProp=dirProps[next];
  925.                 } else {
  926.                     nextDirProp=eor;
  927.                     break;
  928.                 }
  929.             }
  930.  
  931.             if( historyOfEN&PREV_EN_AFTER_W4 ||     /* previous was EN before (W5) */
  932.                 nextDirProp==EN && lastStrong!=AL   /* next is EN and (W2) won't make it AN */
  933.             ) {
  934.                 /* (W5) */
  935.                 if(lastStrong!=L) {
  936.                     dirProp=EN;
  937.                 } else {
  938.                     /* (W7) */
  939.                     dirProp=L;
  940.                 }
  941.             } else {
  942.                 /* (W6) */
  943.                 dirProp=ON;
  944.             }
  945.  
  946.             /* apply the result of (W1), (W5)..(W7) to the entire sequence of ET */
  947.             break;
  948.         case NSM:
  949.             /* (W1) */
  950.             dirProp=prevDirProp;
  951.             /* set historyOfEN back to prevDirProp's historyOfEN */
  952.             historyOfEN>>=EN_SHIFT;
  953.             /*
  954.              * Technically, this should be done before the switch() in the form
  955.              *      if(nextDirProp==NSM) {
  956.              *          dirProps[next]=nextDirProp=dirProp;
  957.              *      }
  958.              *
  959.              * - effectively one iteration ahead.
  960.              * However, whether the next dirProp is NSM or is equal to the current dirProp
  961.              * does not change the outcome of any condition in (W2)..(W7).
  962.              */
  963.             break;
  964.         default:
  965.             break;
  966.         }
  967.  
  968.         /* here, it is always [prev,this,next]dirProp!=BN; it may be next>i+1 */
  969.  
  970.         /* perform (Nn) - here, only L, R, EN, AN, and neutrals are left */
  971.         /* this is one iteration late for the neutrals */
  972.         if(DIRPROP_FLAG(dirProp)&MASK_N) {
  973.             if(neutralStart<0) {
  974.                 /* start of a sequence of neutrals */
  975.                 neutralStart=i;
  976.                 beforeNeutral=prevDirProp;
  977.             }
  978.         } else /* not a neutral, can be only one of { L, R, EN, AN } */ {
  979.             /*
  980.              * Note that all levels[] values are still the same at this
  981.              * point because this function is called for an entire
  982.              * same-level run.
  983.              * Therefore, we need to read only one actual level.
  984.              */
  985.             UBiDiLevel level=levels[i];
  986.  
  987.             if(neutralStart>=0) {
  988.                 UBiDiLevel final;
  989.                 /* end of a sequence of neutrals (dirProp is "afterNeutral") */
  990.                 if(beforeNeutral==L) {
  991.                     if(dirProp==L) {
  992.                         final=0;                /* make all neutrals L (N1) */
  993.                     } else {
  994.                         final=level;            /* make all neutrals "e" (N2) */
  995.                     }
  996.                 } else /* beforeNeutral is one of { R, EN, AN } */ {
  997.                     if(dirProp==L) {
  998.                         final=level;            /* make all neutrals "e" (N2) */
  999.                     } else {
  1000.                         final=1;                /* make all neutrals R (N1) */
  1001.                     }
  1002.                 }
  1003.                 /* perform (In) on the sequence of neutrals */
  1004.                 if((level^final)&1) {
  1005.                     /* do something only if we need to _change_ the level */
  1006.                     do {
  1007.                         ++levels[neutralStart];
  1008.                     } while(++neutralStart<i);
  1009.                 }
  1010.                 neutralStart=-1;
  1011.             }
  1012.  
  1013.             /* perform (In) on the non-neutral character */
  1014.             /*
  1015.              * in the cases of (W5), processing a sequence of ET,
  1016.              * and of (X9), skipping BN,
  1017.              * there may be multiple characters from i to <next
  1018.              * that all get (virtually) the same dirProp and (really) the same level
  1019.              */
  1020.             if(dirProp==L) {
  1021.                 if(level&1) {
  1022.                     ++level;
  1023.                 } else {
  1024.                     i=next;     /* we keep the levels */
  1025.                 }
  1026.             } else if(dirProp==R) {
  1027.                 if(!(level&1)) {
  1028.                     ++level;
  1029.                 } else {
  1030.                     i=next;     /* we keep the levels */
  1031.                 }
  1032.             } else /* EN or AN */ {
  1033.                 level=(level+2)&~1;     /* least greater even level */
  1034.             }
  1035.  
  1036.             /* apply the new level to the sequence, if necessary */
  1037.             while(i<next) {
  1038.                 levels[i++]=level;
  1039.             }
  1040.         }
  1041.     }
  1042.  
  1043.     /* perform (Nn) - here,
  1044.        the character after the the neutrals is eor, which is either L or R */
  1045.     /* this is one iteration late for the neutrals */
  1046.     if(neutralStart>=0) {
  1047.         /*
  1048.          * Note that all levels[] values are still the same at this
  1049.          * point because this function is called for an entire
  1050.          * same-level run.
  1051.          * Therefore, we need to read only one actual level.
  1052.          */
  1053.         UBiDiLevel level=levels[neutralStart], final;
  1054.  
  1055.         /* end of a sequence of neutrals (eor is "afterNeutral") */
  1056.         if(beforeNeutral==L) {
  1057.             if(eor==L) {
  1058.                 final=0;                /* make all neutrals L (N1) */
  1059.             } else {
  1060.                 final=level;            /* make all neutrals "e" (N2) */
  1061.             }
  1062.         } else /* beforeNeutral is one of { R, EN, AN } */ {
  1063.             if(eor==L) {
  1064.                 final=level;            /* make all neutrals "e" (N2) */
  1065.             } else {
  1066.                 final=1;                /* make all neutrals R (N1) */
  1067.             }
  1068.         }
  1069.         /* perform (In) on the sequence of neutrals */
  1070.         if((level^final)&1) {
  1071.             /* do something only if we need to _change_ the level */
  1072.             do {
  1073.                 ++levels[neutralStart];
  1074.             } while(++neutralStart<limit);
  1075.         }
  1076.     }
  1077. }
  1078.  
  1079. /* perform (L1) and (X9) ---------------------------------------------------- */
  1080.  
  1081. /*
  1082.  * Reset the embedding levels for some non-graphic characters (L1).
  1083.  * This function also sets appropriate levels for BN, and
  1084.  * explicit embedding types that are supposed to have been removed
  1085.  * from the paragraph in (X9).
  1086.  */
  1087. static void
  1088. adjustWSLevels(UBiDi *pBiDi) {
  1089.     const DirProp *dirProps=pBiDi->dirProps;
  1090.     UBiDiLevel *levels=pBiDi->levels;
  1091.     UTextOffset i;
  1092.  
  1093.     if(pBiDi->flags&MASK_WS) {
  1094.         UBiDiLevel paraLevel=pBiDi->paraLevel;
  1095.         Flags flag;
  1096.  
  1097.         i=pBiDi->trailingWSStart;
  1098.         while(i>0) {
  1099.             /* reset a sequence of WS/BN before eop and B/S to the paragraph paraLevel */
  1100.             while(i>0 && DIRPROP_FLAG(dirProps[--i])&MASK_WS) {
  1101.                 levels[i]=paraLevel;
  1102.             }
  1103.  
  1104.             /* reset BN to the next character's paraLevel until B/S, which restarts above loop */
  1105.             /* here, i+1 is guaranteed to be <length */
  1106.             while(i>0) {
  1107.                 flag=DIRPROP_FLAG(dirProps[--i]);
  1108.                 if(flag&MASK_BN_EXPLICIT) {
  1109.                     levels[i]=levels[i+1];
  1110.                 } else if(flag&MASK_B_S) {
  1111.                     levels[i]=paraLevel;
  1112.                     break;
  1113.                 }
  1114.             }
  1115.         }
  1116.     }
  1117.  
  1118.     /* now remove the UBIDI_LEVEL_OVERRIDE flags, if any */
  1119.     /* (a separate loop can be optimized more easily by a compiler) */
  1120.     if(pBiDi->flags&MASK_OVERRIDE) {
  1121.         for(i=pBiDi->trailingWSStart; i>0;) {
  1122.             levels[--i]&=~UBIDI_LEVEL_OVERRIDE;
  1123.         }
  1124.     }
  1125. }
  1126.  
  1127. /* -------------------------------------------------------------------------- */
  1128.  
  1129. U_CAPI UBiDiDirection U_EXPORT2
  1130. ubidi_getDirection(const UBiDi *pBiDi) {
  1131.     if(pBiDi!=NULL) {
  1132.         return pBiDi->direction;
  1133.     } else {
  1134.         return UBIDI_LTR;
  1135.     }
  1136. }
  1137.  
  1138. U_CAPI UTextOffset U_EXPORT2
  1139. ubidi_getLength(const UBiDi *pBiDi) {
  1140.     if(pBiDi!=NULL) {
  1141.         return pBiDi->length;
  1142.     } else {
  1143.         return 0;
  1144.     }
  1145. }
  1146.  
  1147. U_CAPI UBiDiLevel U_EXPORT2
  1148. ubidi_getParaLevel(const UBiDi *pBiDi) {
  1149.     if(pBiDi!=NULL) {
  1150.         return pBiDi->paraLevel;
  1151.     } else {
  1152.         return 0;
  1153.     }
  1154. }
  1155.  
  1156. /* statetable prototype ----------------------------------------------------- */
  1157.  
  1158. /*
  1159.  * This is here for possible future
  1160.  * performance work and is not compiled right now.
  1161.  */
  1162.  
  1163. #if 0
  1164. /*
  1165.  * This is a piece of code that could be part of ubidi.c/resolveImplicitLevels().
  1166.  * It replaces in the (Wn) state machine the switch()-if()-cascade with
  1167.  * just a few if()s and a state table.
  1168.  */
  1169.  
  1170. /* use the state table only for the following dirProp's */
  1171. #define MASK_W_TABLE (FLAG(L)|FLAG(R)|FLAG(AL)|FLAG(EN)|FLAG(ES)|FLAG(CS)|FLAG(ET)|FLAG(AN))
  1172.  
  1173. /*
  1174.  * inputs:
  1175.  *
  1176.  * 0..1 historyOfEN - 2b
  1177.  * 2    prevDirProp==AN - 1b
  1178.  * 3..4 lastStrong, one of { L, R, AL, none } - 2b
  1179.  * 5..7 dirProp, one of { L, R, AL, EN, ES, CS, ET, AN } - 3b
  1180.  * 8..9 nextDirProp, one of { EN, AN, other }
  1181.  *
  1182.  * total: 10b=1024 states
  1183.  */
  1184. enum { _L, _R, _AL, _EN, _ES, _CS, _ET, _AN, _OTHER };  /* lastStrong, dirProp */
  1185. enum { __EN, __AN, __OTHER };                           /* nextDirProp */
  1186.  
  1187. #define LAST_STRONG_SHIFT 3
  1188. #define DIR_PROP_SHIFT 5
  1189. #define NEXT_DIR_PROP_SHIFT 8
  1190.  
  1191. /* masks after shifting */
  1192. #define LAST_STRONG_MASK 3
  1193. #define DIR_PROP_MASK 7
  1194. #define STATE_MASK 0x1f
  1195.  
  1196. /* convert dirProp into _dirProp (above enum) */
  1197. static DirProp inputDirProp[dirPropCount]={ _X<<DIR_PROP_SHIFT, ... };
  1198.  
  1199. /* convert dirProp into __dirProp (above enum) */
  1200. static DirProp inputNextDirProp[dirPropCount]={ __X<<NEXT_DIR_PROP_SHIFT, ... };
  1201.  
  1202. /*
  1203.  * outputs:
  1204.  *
  1205.  * dirProp, one of { L, R, EN, AN, ON } - 3b
  1206.  *
  1207.  * 0..1 historyOfEN - 2b
  1208.  * 2    prevDirProp==AN - 1b
  1209.  * 3..4 lastStrong, one of { L, R, AL, none } - 2b
  1210.  * 5..7 new dirProp, one of { L, R, EN, AN, ON }
  1211.  *
  1212.  * total: 8 bits=1 byte per state
  1213.  */
  1214. enum { ___L, ___R, ___EN, ___AN, ___ON, ___count };
  1215.  
  1216. /* convert ___dirProp into dirProp (above enum) */
  1217. static DirProp outputDirProp[___count]={ X, ... };
  1218.  
  1219. /* state table */
  1220. static uint8_t wnTable[1024]={ /* calculate with switch()-if()-cascade */ };
  1221.  
  1222. static void
  1223. resolveImplicitLevels(BiDi *pBiDi,
  1224.                       Index start, Index end,
  1225.                       DirProp sor, DirProp eor) {
  1226.     /* new variable */
  1227.     uint8_t state;
  1228.  
  1229.     /* remove variable lastStrong */
  1230.  
  1231.     /* set initial state (set lastStrong, the rest is 0) */
  1232.     state= sor==L ? 0 : _R<<LAST_STRONG_SHIFT;
  1233.  
  1234.     while(next<limit) {
  1235.         /* advance */
  1236.         prevDirProp=dirProp;
  1237.         dirProp=nextDirProp;
  1238.         i=next;
  1239.         do {
  1240.             if(++next<limit) {
  1241.                 nextDirProp=dirProps[next];
  1242.             } else {
  1243.                 nextDirProp=eor;
  1244.                 break;
  1245.             }
  1246.         } while(FLAG(nextDirProp)&MASK_BN_EXPLICIT);
  1247.  
  1248.         /* (W1..W7) */
  1249.         /* ### This may be more efficient with a switch(dirProp). */
  1250.         if(FLAG(dirProp)&MASK_W_TABLE) {
  1251.             state=wnTable[
  1252.                     ((int)state)|
  1253.                     inputDirProp[dirProp]|
  1254.                     inputNextDirProp[nextDirProp]
  1255.             ];
  1256.             dirProp=outputDirProp[state>>DIR_PROP_SHIFT];
  1257.             state&=STATE_MASK;
  1258.         } else if(dirProp==ET) {
  1259.             /* get sequence of ET; advance only next, not current, previous or historyOfEN */
  1260.             while(next<limit && FLAG(nextDirProp)&MASK_ET_NSM_BN /* (W1), (X9) */) {
  1261.                 if(++next<limit) {
  1262.                     nextDirProp=dirProps[next];
  1263.                 } else {
  1264.                     nextDirProp=eor;
  1265.                     break;
  1266.                 }
  1267.             }
  1268.  
  1269.             state=wnTable[
  1270.                     ((int)state)|
  1271.                     _ET<<DIR_PROP_SHIFT|
  1272.                     inputNextDirProp[nextDirProp]
  1273.             ];
  1274.             dirProp=outputDirProp[state>>DIR_PROP_SHIFT];
  1275.             state&=STATE_MASK;
  1276.  
  1277.             /* apply the result of (W1), (W5)..(W7) to the entire sequence of ET */
  1278.         } else if(dirProp==NSM) {
  1279.             /* (W1) */
  1280.             dirProp=prevDirProp;
  1281.             /* keep prevDirProp's EN and AN states! */
  1282.         } else /* other */ {
  1283.             /* set EN and AN states to 0 */
  1284.             state&=LAST_STRONG_MASK<<LAST_STRONG_SHIFT;
  1285.         }
  1286.  
  1287.         /* perform (Nn) and (In) as usual */
  1288.     }
  1289.     /* perform (Nn) and (In) as usual */
  1290. }
  1291. #endif
  1292.