lib/fribidi-bidi.c

   1 /* FriBidi
   2  * fribidi-bidi.c - bidirectional algorithm
   3  *
   4  * $Id: fribidi-bidi.c,v 1.21 2007-03-15 18:09:25 behdad Exp $
   5  * $Author: behdad $
   6  * $Date: 2007-03-15 18:09:25 $
   7  * $Revision: 1.21 $
   8  * $Source: /home/behdad/src/fdo/fribidi/togit/git/../fribidi/fribidi2/lib/fribidi-bidi.c,v $
   9  *
  10  * Authors:
  11  *   Behdad Esfahbod, 2001, 2002, 2004
  12  *   Dov Grobgeld, 1999, 2000
  13  *
  14  * Copyright (C) 2004 Sharif FarsiWeb, Inc
  15  * Copyright (C) 2001,2002 Behdad Esfahbod
  16  * Copyright (C) 1999,2000 Dov Grobgeld
  17  *
  18  * This library is free software; you can redistribute it and/or
  19  * modify it under the terms of the GNU Lesser General Public
  20  * License as published by the Free Software Foundation; either
  21  * version 2.1 of the License, or (at your option) any later version.
  22  *
  23  * This library is distributed in the hope that it will be useful,
  24  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26  * Lesser General Public License for more details.
  27  *
  28  * You should have received a copy of the GNU Lesser General Public License
  29  * along with this library, in a file named COPYING; if not, write to the
  30  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  31  * Boston, MA 02110-1301, USA
  32  *
  33  * For licensing issues, contact <license@farsiweb.info>.
  34  */
  35
  36 #include "common.h"
  37
  38 #include <fribidi-bidi.h>
  39 #include <fribidi-mirroring.h>
  40 #include <fribidi-unicode.h>
  41
  42 #include "mem.h"
  43 #include "bidi-types.h"
  44 #include "run.h"
  45
  46 /*
  47  * This file implements most of Unicode Standard Annex #9, Tracking Number 13.
  48  */
  49
  50 #ifndef MAX
  51 # define MAX(a,b) ((a) > (b) ? (a) : (b))
  52 #endif /* !MAX */
  53
  54 /* Some convenience macros */
  55 #define RL_TYPE(list) ((list)->type)
  56 #define RL_LEN(list) ((list)->len)
  57 #define RL_POS(list) ((list)->pos)
  58 #define RL_LEVEL(list) ((list)->level)
  59
  60 static FriBidiRun *
  61 merge_with_prev (
  62   FriBidiRun *second
  63 )
  64 {
  65   FriBidiRun *first;
  66
  67   fribidi_assert (second);
  68   fribidi_assert (second->next);
  69   first = second->prev;
  70   fribidi_assert (first);
  71
  72   first->next = second->next;
  73   first->next->prev = first;
  74   RL_LEN (first) += RL_LEN (second);
  75   free_run (second);
  76   return first;
  77 }
  78
  79 static void
  80 compact_list (
  81   FriBidiRun *list
  82 )
  83 {
  84   fribidi_assert (list);
  85
  86   if (list->next)
  87     for_run_list (list, list)
  88       if (RL_TYPE (list->prev) == RL_TYPE (list)
  89           && RL_LEVEL (list->prev) == RL_LEVEL (list))
  90       list = merge_with_prev (list);
  91 }
  92
  93 static void
  94 compact_neutrals (
  95   FriBidiRun *list
  96 )
  97 {
  98   fribidi_assert (list);
  99
 100   if (list->next)
 101     {
 102       for_run_list (list, list)
 103       {
 104         if (RL_LEVEL (list->prev) == RL_LEVEL (list)
 105             &&
 106             ((RL_TYPE
 107               (list->prev) == RL_TYPE (list)
 108               || (FRIBIDI_IS_NEUTRAL (RL_TYPE (list->prev))
 109                   && FRIBIDI_IS_NEUTRAL (RL_TYPE (list))))))
 110           list = merge_with_prev (list);
 111       }
 112     }
 113 }
 114
 115 #if DEBUG+0
 116 /*======================================================================
 117  *  For debugging, define some functions for printing the types and the
 118  *  levels.
 119  *----------------------------------------------------------------------*/
 120
 121 static char char_from_level_array[] = {
 122   '$',                          /* -1 == FRIBIDI_SENTINEL, indicating
 123                                  * start or end of string. */
 124   /* 0-61 == 0-9,a-z,A-Z are the the only valid levels before resolving
 125    * implicits.  after that the level @ may be appear too. */
 126   '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 127   'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
 128   'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
 129   'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
 130   'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 131   'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
 132   'Y', 'Z',
 133
 134   '@',                          /* 62 == only must appear after resolving
 135                                  * implicits. */
 136
 137   '!',                          /* 63 == FRIBIDI_LEVEL_INVALID, internal error,
 138                                  * this level shouldn't be seen.  */
 139
 140   '*', '*', '*', '*', '*'       /* >= 64 == overflows, this levels and higher
 141                                  * levels show a real bug!. */
 142 };
 143
 144 #define fribidi_char_from_level(level) char_from_level_array[(level) + 1]
 145
 146 static void
 147 print_types_re (
 148   const FriBidiRun *pp
 149 )
 150 {
 151   fribidi_assert (pp);
 152
 153   MSG ("  Run types  : ");
 154   for_run_list (pp, pp)
 155   {
 156     MSG5 ("%d:%d(%s)[%d] ",
 157           pp->pos, pp->len, fribidi_get_bidi_type_name (pp->type), pp->level);
 158   }
 159   MSG ("\n");
 160 }
 161
 162 static void
 163 print_resolved_levels (
 164   const FriBidiRun *pp
 165 )
 166 {
 167   fribidi_assert (pp);
 168
 169   MSG ("  Res. levels: ");
 170   for_run_list (pp, pp)
 171   {
 172     register FriBidiStrIndex i;
 173     for (i = RL_LEN (pp); i; i--)
 174       MSG2 ("%c", fribidi_char_from_level (RL_LEVEL (pp)));
 175   }
 176   MSG ("\n");
 177 }
 178
 179 static void
 180 print_resolved_types (
 181   const FriBidiRun *pp
 182 )
 183 {
 184   fribidi_assert (pp);
 185
 186   MSG ("  Res. types : ");
 187   for_run_list (pp, pp)
 188   {
 189     FriBidiStrIndex i;
 190     for (i = RL_LEN (pp); i; i--)
 191       MSG2 ("%c", fribidi_char_from_bidi_type (pp->type));
 192   }
 193   MSG ("\n");
 194 }
 195
 196 static void
 197 print_bidi_string (
 198   /* input */
 199   const FriBidiCharType *bidi_types,
 200   const FriBidiStrIndex len
 201 )
 202 {
 203   register FriBidiStrIndex i;
 204
 205   fribidi_assert (bidi_types);
 206
 207   MSG ("  Org. types : ");
 208   for (i = 0; i < len; i++)
 209     MSG2 ("%c", fribidi_char_from_bidi_type (bidi_types[i]));
 210   MSG ("\n");
 211 }
 212 #endif /* DEBUG */
 213
 214
 215 /*=========================================================================
 216  * define macros for push and pop the status in to / out of the stack
 217  *-------------------------------------------------------------------------*/
 218
 219 /* There are a few little points in pushing into and poping from the status
 220    stack:
 221    1. when the embedding level is not valid (more than
 222    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=61), you must reject it, and not to push
 223    into the stack, but when you see a PDF, you must find the matching code,
 224    and if it was pushed in the stack, pop it, it means you must pop if and
 225    only if you have pushed the matching code, the over_pushed var counts the
 226    number of rejected codes so far.
 227    2. there's a more confusing point too, when the embedding level is exactly
 228    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL-1=60, an LRO or LRE is rejected
 229    because the new level would be FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL+1=62, that
 230    is invalid; but an RLO or RLE is accepted because the new level is
 231    FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL=61, that is valid, so the rejected codes
 232    may be not continuous in the logical order, in fact there are at most two
 233    continuous intervals of codes, with an RLO or RLE between them.  To support
 234    this case, the first_interval var counts the number of rejected codes in
 235    the first interval, when it is 0, means that there is only one interval.
 236 */
 237
 238 /* a. If this new level would be valid, then this embedding code is valid.
 239    Remember (push) the current embedding level and override status.
 240    Reset current level to this new level, and reset the override status to
 241    new_override.
 242    b. If the new level would not be valid, then this code is invalid. Don't
 243    change the current level or override status.
 244 */
 245 #define PUSH_STATUS \
 246     FRIBIDI_BEGIN_STMT \
 247       if LIKELY(new_level <= FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL) \
 248         { \
 249           if UNLIKELY(level == FRIBIDI_BIDI_MAX_EXPLICIT_LEVEL - 1) \
 250             first_interval = over_pushed; \
 251           status_stack[stack_size].level = level; \
 252           status_stack[stack_size].override = override; \
 253           stack_size++; \
 254           level = new_level; \
 255           override = new_override; \
 256         } else \
 257           over_pushed++; \
 258     FRIBIDI_END_STMT
 259
 260 /* If there was a valid matching code, restore (pop) the last remembered
 261    (pushed) embedding level and directional override.
 262 */
 263 #define POP_STATUS \
 264     FRIBIDI_BEGIN_STMT \
 265       if (stack_size) \
 266       { \
 267         if UNLIKELY(over_pushed > first_interval) \
 268           over_pushed--; \
 269         else \
 270           { \
 271             if LIKELY(over_pushed == first_interval) \
 272               first_interval = 0; \
 273             stack_size--; \
 274             level = status_stack[stack_size].level; \
 275             override = status_stack[stack_size].override; \
 276           } \
 277       } \
 278     FRIBIDI_END_STMT
 279
 280
 281 /* Return the type of previous run or the SOR, if already at the start of
 282    a level run. */
 283 #define PREV_TYPE_OR_SOR(pp) \
 284     ( \
 285       RL_LEVEL(pp->prev) == RL_LEVEL(pp) ? \
 286         RL_TYPE(pp->prev) : \
 287         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->prev), RL_LEVEL(pp))) \
 288     )
 289
 290 /* Return the type of next run or the EOR, if already at the end of
 291    a level run. */
 292 #define NEXT_TYPE_OR_EOR(pp) \
 293     ( \
 294       RL_LEVEL(pp->next) == RL_LEVEL(pp) ? \
 295         RL_TYPE(pp->next) : \
 296         FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->next), RL_LEVEL(pp))) \
 297     )
 298
 299
 300 /* Return the embedding direction of a link. */
 301 #define FRIBIDI_EMBEDDING_DIRECTION(link) \
 302     FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(link))
 303
 304
 305 FRIBIDI_ENTRY FriBidiParType
 306 fribidi_get_par_direction (
 307   /* input */
 308   const FriBidiCharType *bidi_types,
 309   const FriBidiStrIndex len
 310 )
 311 {
 312   register FriBidiStrIndex i;
 313
 314   fribidi_assert (bidi_types);
 315
 316   for (i = 0; i < len; i++)
 317     if (FRIBIDI_IS_LETTER (bidi_types[i]))
 318       return FRIBIDI_IS_RTL (bidi_types[i]) ? FRIBIDI_PAR_RTL :
 319         FRIBIDI_PAR_LTR;
 320
 321   return FRIBIDI_PAR_ON;
 322 }
 323
 324 FRIBIDI_ENTRY FriBidiLevel
 325 fribidi_get_par_embedding_levels (
 326   /* input */
 327   const FriBidiCharType *bidi_types,
 328   const FriBidiStrIndex len,
 329   /* input and output */
 330   FriBidiParType *pbase_dir,
 331   /* output */
 332   FriBidiLevel *embedding_levels
 333 )
 334 {
 335   FriBidiLevel base_level, max_level = 0;
 336   FriBidiParType base_dir;
 337   FriBidiRun *main_run_list = NULL, *explicits_list = NULL, *pp;
 338   fribidi_boolean status = false;
 339
 340   if UNLIKELY
 341     (!len)
 342     {
 343       status = true;
 344       goto out;
 345     }
 346
 347   DBG ("in fribidi_get_par_embedding_levels");
 348
 349   fribidi_assert (bidi_types);
 350   fribidi_assert (pbase_dir);
 351   fribidi_assert (embedding_levels);
 352
 353   /* Determinate character types */
 354   {
 355     /* Get run-length encoded character types */
 356     main_run_list = run_list_encode_bidi_types (bidi_types, len);
 357     if UNLIKELY
 358       (!main_run_list) goto out;
 359   }
 360
 361   /* Find base level */
 362   /* If no strong base_dir was found, resort to the weak direction
 363      that was passed on input. */
 364   base_level = FRIBIDI_DIR_TO_LEVEL (*pbase_dir);
 365   if (!FRIBIDI_IS_STRONG (*pbase_dir))
 366     /* P2. P3. Search for first strong character and use its direction as
 367        base direction */
 368     {
 369       for_run_list (pp, main_run_list) if (FRIBIDI_IS_LETTER (RL_TYPE (pp)))
 370         {
 371           base_level = FRIBIDI_DIR_TO_LEVEL (RL_TYPE (pp));
 372           *pbase_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 373           break;
 374         }
 375     }
 376   base_dir = FRIBIDI_LEVEL_TO_DIR (base_level);
 377   DBG2 ("  base level : %c", fribidi_char_from_level (base_level));
 378   DBG2 ("  base dir   : %c", fribidi_char_from_bidi_type (base_dir));
 379
 380 # if DEBUG
 381   if UNLIKELY
 382     (fribidi_debug_status ())
 383     {
 384       print_types_re (main_run_list);
 385     }
 386 # endif /* DEBUG */
 387
 388   /* Explicit Levels and Directions */
 389   DBG ("explicit levels and directions");
 390   {
 391     FriBidiLevel level, new_level;
 392     FriBidiCharType override, new_override;
 393     FriBidiStrIndex i;
 394     int stack_size, over_pushed, first_interval;
 395     struct
 396     {
 397       FriBidiCharType override; /* only LTR, RTL and ON are valid */
 398       FriBidiLevel level;
 399     } *status_stack;
 400     FriBidiRun temp_link;
 401
 402 /* explicits_list is a list like main_run_list, that holds the explicit
 403    codes that are removed from main_run_list, to reinsert them later by
 404    calling the shadow_run_list.
 405 */
 406     explicits_list = new_run_list ();
 407     if UNLIKELY
 408       (!explicits_list) goto out;
 409
 410     /* X1. Begin by setting the current embedding level to the paragraph
 411        embedding level. Set the directional override status to neutral.
 412        Process each character iteratively, applying rules X2 through X9.
 413        Only embedding levels from 0 to 61 are valid in this phase. */
 414
 415     level = base_level;
 416     override = FRIBIDI_TYPE_ON;
 417     /* stack */
 418     stack_size = 0;
 419     over_pushed = 0;
 420     first_interval = 0;
 421     status_stack = fribidi_malloc (sizeof (status_stack[0]) *
 422                                    FRIBIDI_BIDI_MAX_RESOLVED_LEVELS);
 423
 424     for_run_list (pp, main_run_list)
 425     {
 426       FriBidiCharType this_type = RL_TYPE (pp);
 427       if (FRIBIDI_IS_EXPLICIT_OR_BN (this_type))
 428         {
 429           if (FRIBIDI_IS_STRONG (this_type))
 430             {                   /* LRE, RLE, LRO, RLO */
 431               /* 1. Explicit Embeddings */
 432               /*   X2. With each RLE, compute the least greater odd
 433                  embedding level. */
 434               /*   X3. With each LRE, compute the least greater even
 435                  embedding level. */
 436               /* 2. Explicit Overrides */
 437               /*   X4. With each RLO, compute the least greater odd
 438                  embedding level. */
 439               /*   X5. With each LRO, compute the least greater even
 440                  embedding level. */
 441               new_override = FRIBIDI_EXPLICIT_TO_OVERRIDE_DIR (this_type);
 442               for (i = RL_LEN (pp); i; i--)
 443                 {
 444                   new_level =
 445                     ((level + FRIBIDI_DIR_TO_LEVEL (this_type) + 2) & ~1) -
 446                     FRIBIDI_DIR_TO_LEVEL (this_type);
 447                   PUSH_STATUS;
 448                 }
 449             }
 450           else if (this_type == FRIBIDI_TYPE_PDF)
 451             {
 452               /* 3. Terminating Embeddings and overrides */
 453               /*   X7. With each PDF, determine the matching embedding or
 454                  override code. */
 455               for (i = RL_LEN (pp); i; i--)
 456                 POP_STATUS;
 457             }
 458
 459           /* X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes. */
 460           /* Remove element and add it to explicits_list */
 461           RL_LEVEL (pp) = FRIBIDI_SENTINEL;
 462           temp_link.next = pp->next;
 463           move_node_before (pp, explicits_list);
 464           pp = &temp_link;
 465         }
 466       else
 467         {
 468           /* X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
 469              a. Set the level of the current character to the current
 470              embedding level.
 471              b. Whenever the directional override status is not neutral,
 472              reset the current character type to the directional override
 473              status. */
 474           RL_LEVEL (pp) = level;
 475           if (!FRIBIDI_IS_NEUTRAL (override))
 476             RL_TYPE (pp) = override;
 477         }
 478       /* X8. All explicit directional embeddings and overrides are
 479          completely terminated at the end of each paragraph. Paragraph
 480          separators are not included in the embedding. */
 481       /* This function is running on a single paragraph, so we can do
 482          X8 after all the input is processed. */
 483     }
 484
 485     /* Implementing X8. It has no effect on a single paragraph! */
 486     level = base_level;
 487     override = FRIBIDI_TYPE_ON;
 488     stack_size = 0;
 489     over_pushed = 0;
 490
 491     fribidi_free (status_stack);
 492   }
 493   /* X10. The remaining rules are applied to each run of characters at the
 494      same level. For each run, determine the start-of-level-run (sor) and
 495      end-of-level-run (eor) type, either L or R. This depends on the
 496      higher of the two levels on either side of the boundary (at the start
 497      or end of the paragraph, the level of the 'other' run is the base
 498      embedding level). If the higher level is odd, the type is R, otherwise
 499      it is L. */
 500   /* Resolving Implicit Levels can be done out of X10 loop, so only change
 501      of Resolving Weak Types and Resolving Neutral Types is needed. */
 502
 503   compact_list (main_run_list);
 504
 505 # if DEBUG
 506   if UNLIKELY
 507     (fribidi_debug_status ())
 508     {
 509       print_types_re (main_run_list);
 510       print_bidi_string (bidi_types, len);
 511       print_resolved_levels (main_run_list);
 512       print_resolved_types (main_run_list);
 513     }
 514 # endif /* DEBUG */
 515
 516   /* 4. Resolving weak types */
 517   DBG ("resolving weak types");
 518   {
 519     FriBidiCharType last_strong, prev_type_orig;
 520     fribidi_boolean w4;
 521
 522     last_strong = base_dir;
 523
 524     for_run_list (pp, main_run_list)
 525     {
 526       register FriBidiCharType prev_type, this_type, next_type;
 527
 528       prev_type = PREV_TYPE_OR_SOR (pp);
 529       this_type = RL_TYPE (pp);
 530       next_type = NEXT_TYPE_OR_EOR (pp);
 531
 532       if (FRIBIDI_IS_STRONG (prev_type))
 533         last_strong = prev_type;
 534
 535       /* W1. NSM
 536          Examine each non-spacing mark (NSM) in the level run, and change the
 537          type of the NSM to the type of the previous character. If the NSM
 538          is at the start of the level run, it will get the type of sor. */
 539       /* Implementation note: it is important that if the previous character
 540          is not sor, then we should merge this run with the previous,
 541          because of rules like W5, that we assume all of a sequence of
 542          adjacent ETs are in one FriBidiRun. */
 543       if (this_type == FRIBIDI_TYPE_NSM)
 544         {
 545           if (RL_LEVEL (pp->prev) == RL_LEVEL (pp))
 546             pp = merge_with_prev (pp);
 547           else
 548             RL_TYPE (pp) = prev_type;
 549           continue;             /* As we know the next condition cannot be true. */
 550         }
 551
 552       /* W2: European numbers. */
 553       if (this_type == FRIBIDI_TYPE_EN && last_strong == FRIBIDI_TYPE_AL)
 554         {
 555           RL_TYPE (pp) = FRIBIDI_TYPE_AN;
 556
 557           /* Resolving dependency of loops for rules W1 and W2, so we
 558              can merge them in one loop. */
 559           if (next_type == FRIBIDI_TYPE_NSM)
 560             RL_TYPE (pp->next) = FRIBIDI_TYPE_AN;
 561         }
 562     }
 563
 564
 565     last_strong = base_dir;
 566     /* Resolving dependency of loops for rules W4 and W5, W5 may
 567        want to prevent W4 to take effect in the next turn, do this
 568        through "w4". */
 569     w4 = true;
 570     /* Resolving dependency of loops for rules W4 and W5 with W7,
 571        W7 may change an EN to L but it sets the prev_type_orig if needed,
 572        so W4 and W5 in next turn can still do their works. */
 573     prev_type_orig = FRIBIDI_TYPE_ON;
 574
 575     for_run_list (pp, main_run_list)
 576     {
 577       register FriBidiCharType prev_type, this_type, next_type;
 578
 579       prev_type = PREV_TYPE_OR_SOR (pp);
 580       this_type = RL_TYPE (pp);
 581       next_type = NEXT_TYPE_OR_EOR (pp);
 582
 583       if (FRIBIDI_IS_STRONG (prev_type))
 584         last_strong = prev_type;
 585
 586       /* W3: Change ALs to R. */
 587       if (this_type == FRIBIDI_TYPE_AL)
 588         {
 589           RL_TYPE (pp) = FRIBIDI_TYPE_RTL;
 590           w4 = true;
 591           prev_type_orig = FRIBIDI_TYPE_ON;
 592           continue;
 593         }
 594
 595       /* W4. A single european separator changes to a european number.
 596          A single common separator between two numbers of the same type
 597          changes to that type. */
 598       if (w4
 599           && RL_LEN (pp) == 1 && FRIBIDI_IS_ES_OR_CS (this_type)
 600           && FRIBIDI_IS_NUMBER (prev_type_orig)
 601           && prev_type_orig == next_type
 602           && (prev_type_orig == FRIBIDI_TYPE_EN
 603               || this_type == FRIBIDI_TYPE_CS))
 604         {
 605           RL_TYPE (pp) = prev_type;
 606           this_type = RL_TYPE (pp);
 607         }
 608       w4 = true;
 609
 610       /* W5. A sequence of European terminators adjacent to European
 611          numbers changes to All European numbers. */
 612       if (this_type == FRIBIDI_TYPE_ET
 613           && (prev_type_orig == FRIBIDI_TYPE_EN
 614               || next_type == FRIBIDI_TYPE_EN))
 615         {
 616           RL_TYPE (pp) = FRIBIDI_TYPE_EN;
 617           w4 = false;
 618           this_type = RL_TYPE (pp);
 619         }
 620
 621       /* W6. Otherwise change separators and terminators to other neutral. */
 622       if (FRIBIDI_IS_NUMBER_SEPARATOR_OR_TERMINATOR (this_type))
 623         RL_TYPE (pp) = FRIBIDI_TYPE_ON;
 624
 625       /* W7. Change european numbers to L. */
 626       if (this_type == FRIBIDI_TYPE_EN && last_strong == FRIBIDI_TYPE_LTR)
 627         {
 628           RL_TYPE (pp) = FRIBIDI_TYPE_LTR;
 629           prev_type_orig = (RL_LEVEL (pp) == RL_LEVEL (pp->next) ?
 630                             FRIBIDI_TYPE_EN : FRIBIDI_TYPE_ON);
 631         }
 632       else
 633         prev_type_orig = PREV_TYPE_OR_SOR (pp->next);
 634     }
 635   }
 636
 637   compact_neutrals (main_run_list);
 638
 639 # if DEBUG
 640   if UNLIKELY
 641     (fribidi_debug_status ())
 642     {
 643       print_resolved_levels (main_run_list);
 644       print_resolved_types (main_run_list);
 645     }
 646 # endif /* DEBUG */
 647
 648   /* 5. Resolving Neutral Types */
 649   DBG ("resolving neutral types");
 650   {
 651     /* N1. and N2.
 652        For each neutral, resolve it. */
 653     for_run_list (pp, main_run_list)
 654     {
 655       FriBidiCharType prev_type, this_type, next_type;
 656
 657       /* "European and Arabic numbers are treated as though they were R"
 658          FRIBIDI_CHANGE_NUMBER_TO_RTL does this. */
 659       this_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (RL_TYPE (pp));
 660       prev_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (PREV_TYPE_OR_SOR (pp));
 661       next_type = FRIBIDI_CHANGE_NUMBER_TO_RTL (NEXT_TYPE_OR_EOR (pp));
 662
 663       if (FRIBIDI_IS_NEUTRAL (this_type))
 664         RL_TYPE (pp) = (prev_type == next_type) ?
 665           /* N1. */ prev_type :
 666           /* N2. */ FRIBIDI_EMBEDDING_DIRECTION (pp);
 667     }
 668   }
 669
 670   compact_list (main_run_list);
 671
 672 # if DEBUG
 673   if UNLIKELY
 674     (fribidi_debug_status ())
 675     {
 676       print_resolved_levels (main_run_list);
 677       print_resolved_types (main_run_list);
 678     }
 679 # endif /* DEBUG */
 680
 681   /* 6. Resolving implicit levels */
 682   DBG ("resolving implicit levels");
 683   {
 684     max_level = base_level;
 685
 686     for_run_list (pp, main_run_list)
 687     {
 688       FriBidiCharType this_type;
 689       int level;
 690
 691       this_type = RL_TYPE (pp);
 692       level = RL_LEVEL (pp);
 693
 694       /* I1. Even */
 695       /* I2. Odd */
 696       if (FRIBIDI_IS_NUMBER (this_type))
 697         RL_LEVEL (pp) = (level + 2) & ~1;
 698       else
 699         RL_LEVEL (pp) =
 700           level +
 701           (FRIBIDI_LEVEL_IS_RTL (level) ^ FRIBIDI_DIR_TO_LEVEL (this_type));
 702
 703       if (RL_LEVEL (pp) > max_level)
 704         max_level = RL_LEVEL (pp);
 705     }
 706   }
 707
 708   compact_list (main_run_list);
 709
 710 # if DEBUG
 711   if UNLIKELY
 712     (fribidi_debug_status ())
 713     {
 714       print_bidi_string (bidi_types, len);
 715       print_resolved_levels (main_run_list);
 716       print_resolved_types (main_run_list);
 717     }
 718 # endif /* DEBUG */
 719
 720 /* Reinsert the explicit codes & BN's that are already removed, from the
 721    explicits_list to main_run_list. */
 722   DBG ("reinserting explicit codes");
 723   if UNLIKELY
 724     (explicits_list->next != explicits_list)
 725     {
 726       register FriBidiRun *p;
 727       register fribidi_boolean stat =
 728         shadow_run_list (main_run_list, explicits_list, true);
 729       explicits_list = NULL;
 730       if UNLIKELY
 731         (!stat) goto out;
 732
 733       /* Set level of inserted explicit chars to that of their previous
 734        * char, such that they do not affect reordering. */
 735       p = main_run_list->next;
 736       if (p != main_run_list && p->level == FRIBIDI_SENTINEL)
 737         p->level = base_level;
 738       for_run_list (p, main_run_list) if (p->level == FRIBIDI_SENTINEL)
 739         p->level = p->prev->level;
 740     }
 741
 742 # if DEBUG
 743   if UNLIKELY
 744     (fribidi_debug_status ())
 745     {
 746       print_types_re (main_run_list);
 747       print_resolved_levels (main_run_list);
 748       print_resolved_types (main_run_list);
 749     }
 750 # endif /* DEBUG */
 751
 752   DBG ("reset the embedding levels, 1, 2, 3.");
 753   {
 754     register int j, state, pos;
 755     register FriBidiCharType char_type;
 756     register FriBidiRun *p, *q, *list;
 757
 758     /* L1. Reset the embedding levels of some chars:
 759        1. segment separators,
 760        2. paragraph separators,
 761        3. any sequence of whitespace characters preceding a segment
 762        separator or paragraph separator, and
 763        ... (to be continued in fribidi_reorder_line()). */
 764     list = new_run_list ();
 765     if UNLIKELY
 766       (!list) goto out;
 767     q = list;
 768     state = 1;
 769     pos = len - 1;
 770     for (j = len - 1; j >= -1; j--)
 771       {
 772         /* close up the open link at the end */
 773         if (j >= 0)
 774           char_type = bidi_types[j];
 775         else
 776           char_type = FRIBIDI_TYPE_ON;
 777         if (!state && FRIBIDI_IS_SEPARATOR (char_type))
 778           {
 779             state = 1;
 780             pos = j;
 781           }
 782         else if (state && !FRIBIDI_IS_EXPLICIT_OR_SEPARATOR_OR_BN_OR_WS
 783                  (char_type))
 784           {
 785             state = 0;
 786             p = new_run ();
 787             if UNLIKELY
 788               (!p)
 789               {
 790                 free_run_list (list);
 791                 goto out;
 792               }
 793             p->pos = j + 1;
 794             p->len = pos - j;
 795             p->type = base_dir;
 796             p->level = base_level;
 797             move_node_before (p, q);
 798             q = p;
 799           }
 800       }
 801     if UNLIKELY
 802       (!shadow_run_list (main_run_list, list, false)) goto out;
 803   }
 804
 805 # if DEBUG
 806   if UNLIKELY
 807     (fribidi_debug_status ())
 808     {
 809       print_types_re (main_run_list);
 810       print_resolved_levels (main_run_list);
 811       print_resolved_types (main_run_list);
 812     }
 813 # endif /* DEBUG */
 814
 815   {
 816     FriBidiStrIndex pos = 0;
 817     for_run_list (pp, main_run_list)
 818     {
 819       register FriBidiStrIndex l;
 820       register FriBidiLevel level = pp->level;
 821       for (l = pp->len; l; l--)
 822         embedding_levels[pos++] = level;
 823     }
 824   }
 825
 826   status = true;
 827
 828 out:
 829   DBG ("leaving fribidi_get_par_embedding_levels");
 830
 831   if (main_run_list)
 832     free_run_list (main_run_list);
 833   if UNLIKELY
 834     (explicits_list) free_run_list (explicits_list);
 835
 836   return status ? max_level + 1 : 0;
 837 }
 838
 839
 840 static void
 841 bidi_string_reverse (
 842   FriBidiChar *str,
 843   const FriBidiStrIndex len
 844 )
 845 {
 846   FriBidiStrIndex i;
 847
 848   fribidi_assert (str);
 849
 850   for (i = 0; i < len / 2; i++)
 851     {
 852       FriBidiChar tmp = str[i];
 853       str[i] = str[len - 1 - i];
 854       str[len - 1 - i] = tmp;
 855     }
 856 }
 857
 858 static void
 859 index_array_reverse (
 860   FriBidiStrIndex *arr,
 861   const FriBidiStrIndex len
 862 )
 863 {
 864   FriBidiStrIndex i;
 865
 866   fribidi_assert (arr);
 867
 868   for (i = 0; i < len / 2; i++)
 869     {
 870       FriBidiStrIndex tmp = arr[i];
 871       arr[i] = arr[len - 1 - i];
 872       arr[len - 1 - i] = tmp;
 873     }
 874 }
 875
 876
 877 FRIBIDI_ENTRY FriBidiLevel
 878 fribidi_reorder_line (
 879   /* input */
 880   FriBidiFlags flags, /* reorder flags */
 881   const FriBidiCharType *bidi_types,
 882   const FriBidiStrIndex len,
 883   const FriBidiStrIndex off,
 884   const FriBidiParType base_dir,
 885   /* input and output */
 886   FriBidiLevel *embedding_levels,
 887   FriBidiChar *visual_str,
 888   /* output */
 889   FriBidiStrIndex *map
 890 )
 891 {
 892   fribidi_boolean status = false;
 893   FriBidiLevel max_level = 0;
 894
 895   if UNLIKELY
 896     (len == 0)
 897     {
 898       status = true;
 899       goto out;
 900     }
 901
 902   DBG ("in fribidi_reorder_line");
 903
 904   fribidi_assert (bidi_types);
 905   fribidi_assert (embedding_levels);
 906
 907   DBG ("reset the embedding levels, 4. whitespace at the end of line");
 908   {
 909     register FriBidiStrIndex i;
 910
 911     /* L1. Reset the embedding levels of some chars:
 912        4. any sequence of white space characters at the end of the line. */
 913     for (i = off + len - 1; i >= off &&
 914          FRIBIDI_IS_EXPLICIT_OR_BN_OR_WS (bidi_types[i]); i--)
 915       embedding_levels[i] = FRIBIDI_DIR_TO_LEVEL (base_dir);
 916   }
 917
 918   /* 7. Reordering resolved levels */
 919   {
 920     register FriBidiLevel level;
 921     register FriBidiStrIndex i;
 922
 923     /* Reorder both the outstring and the order array */
 924     {
 925       if (FRIBIDI_TEST_BITS (flags, FRIBIDI_FLAG_REORDER_NSM))
 926         {
 927           /* L3. Reorder NSMs. */
 928           for (i = off + len - 1; i >= off; i--)
 929             if (FRIBIDI_LEVEL_IS_RTL (embedding_levels[i])
 930                 && bidi_types[i] == FRIBIDI_TYPE_NSM)
 931               {
 932                 register FriBidiStrIndex seq_end = i;
 933                 level = embedding_levels[i];
 934
 935                 for (i--; i >= off &&
 936                      FRIBIDI_IS_EXPLICIT_OR_BN_OR_NSM (bidi_types[i])
 937                      && embedding_levels[i] == level; i--)
 938                   ;
 939
 940                 if (i < off || embedding_levels[i] != level)
 941                   {
 942                     i++;
 943                     DBG ("warning: NSM(s) at the beggining of level run");
 944                   }
 945
 946                 if (visual_str)
 947                   {
 948                     bidi_string_reverse (visual_str + i, seq_end - i + 1);
 949                   }
 950                 if (map)
 951                   {
 952                     index_array_reverse (map + i, seq_end - i + 1);
 953                   }
 954               }
 955         }
 956
 957       /* Find max_level of the line.  We don't reuse the paragraph
 958        * max_level, both for a cleaner API, and that the line max_level
 959        * may be far less than paragraph max_level. */
 960       for (i = off + len - 1; i >= off; i--)
 961         if (embedding_levels[i] > max_level)
 962           max_level = embedding_levels[i];
 963
 964       /* L2. Reorder. */
 965       for (level = max_level; level > 0; level--)
 966         for (i = off + len - 1; i >= off; i--)
 967           if (embedding_levels[i] >= level)
 968             {
 969               /* Find all stretches that are >= level_idx */
 970               register FriBidiStrIndex seq_end = i;
 971               for (i--; i >= off && embedding_levels[i] >= level; i--)
 972                 ;
 973
 974               if (visual_str)
 975                 bidi_string_reverse (visual_str + i + 1, seq_end - i);
 976               if (map)
 977                 index_array_reverse (map + i + 1, seq_end - i);
 978             }
 979     }
 980
 981   }
 982
 983   status = true;
 984
 985 out:
 986
 987   return status ? max_level + 1 : 0;
 988 }
 989
 990 /* Editor directions:
 991  * vim:textwidth=78:tabstop=8:shiftwidth=2:autoindent:cindent
 992  */