nsBidi.cpp

/* -*- Mode: C; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 *
 * ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is mozilla.org code.
 *
 * The Initial Developer of the Original Code is
 * IBM Corporation.
 * Portions created by the Initial Developer are Copyright (C) 2000
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Simon Montagu
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either of the GNU General Public License Version 2 or later (the "GPL"),
 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */
#ifdef IBMBIDI

#include "prmem.h"
#include "nsBidi.h"
#include "nsBidiUtils.h"
#include "nsCRT.h"

// These are #defined in <sys/regset.h> under Solaris 10 x86
#undef CS
#undef ES

/*  Comparing the description of the Bidi algorithm with this implementation
    is easier with the same names for the Bidi types in the code as there.
*/
enum { 
    L =   eCharType_LeftToRight,
    R =   eCharType_RightToLeft,
    EN =  eCharType_EuropeanNumber,
    ES =  eCharType_EuropeanNumberSeparator,
    ET =  eCharType_EuropeanNumberTerminator,
    AN =  eCharType_ArabicNumber,
    CS =  eCharType_CommonNumberSeparator,
    B =   eCharType_BlockSeparator,
    S =   eCharType_SegmentSeparator,
    WS =  eCharType_WhiteSpaceNeutral,
    O_N = eCharType_OtherNeutral,
    LRE = eCharType_LeftToRightEmbedding,
    LRO = eCharType_LeftToRightOverride,
    AL =  eCharType_RightToLeftArabic,
    RLE = eCharType_RightToLeftEmbedding,
    RLO = eCharType_RightToLeftOverride,
    PDF = eCharType_PopDirectionalFormat,
    NSM = eCharType_DirNonSpacingMark,
    BN =  eCharType_BoundaryNeutral,
    dirPropCount
};

/* to avoid some conditional statements, use tiny constant arrays */
static Flags flagLR[2]={ DIRPROP_FLAG(L), DIRPROP_FLAG(R) };
static Flags flagE[2]={ DIRPROP_FLAG(LRE), DIRPROP_FLAG(RLE) };
static Flags flagO[2]={ DIRPROP_FLAG(LRO), DIRPROP_FLAG(RLO) };

#define DIRPROP_FLAG_LR(level) flagLR[(level)&1]
#define DIRPROP_FLAG_E(level) flagE[(level)&1]
#define DIRPROP_FLAG_O(level) flagO[(level)&1]

/*
 * General implementation notes:
 *
 * Throughout the implementation, there are comments like (W2) that refer to
 * rules of the Bidi algorithm in its version 5, in this example to the second
 * rule of the resolution of weak types.
 *
 * For handling surrogate pairs, where two UChar's form one "abstract" (or UTF-32)
 * character according to UTF-16, the second UChar gets the directional property of
 * the entire character assigned, while the first one gets a BN, a boundary
 * neutral, type, which is ignored by most of the algorithm according to
 * rule (X9) and the implementation suggestions of the Bidi algorithm.
 *
 * Later, AdjustWSLevels() will set the level for each BN to that of the
 * following character (UChar), which results in surrogate pairs getting the
 * same level on each of their surrogates.
 *
 * In a UTF-8 implementation, the same thing could be done: the last byte of
 * a multi-byte sequence would get the "real" property, while all previous
 * bytes of that sequence would get BN.
 *
 * It is not possible to assign all those parts of a character the same real
 * property because this would fail in the resolution of weak types with rules
 * that look at immediately surrounding types.
 *
 * As a related topic, this implementation does not remove Boundary Neutral
 * types from the input, but ignores them whenever this is relevant.
 * For example, the loop for the resolution of the weak types reads
 * types until it finds a non-BN.
 * Also, explicit embedding codes are neither changed into BN nor removed.
 * They are only treated the same way real BNs are.
 * As stated before, AdjustWSLevels() takes care of them at the end.
 * For the purpose of conformance, the levels of all these codes
 * do not matter.
 *
 * Note that this implementation never modifies the dirProps
 * after the initial setup.
 *
 *
 * In this implementation, the resolution of weak types (Wn),
 * neutrals (Nn), and the assignment of the resolved level (In)
 * are all done in one single loop, in ResolveImplicitLevels().
 * Changes of dirProp values are done on the fly, without writing
 * them back to the dirProps array.
 *
 *
 * This implementation contains code that allows to bypass steps of the
 * algorithm that are not needed on the specific paragraph
 * in order to speed up the most common cases considerably,
 * like text that is entirely LTR, or RTL text without numbers.
 *
 * Most of this is done by setting a bit for each directional property
 * in a flags variable and later checking for whether there are
 * any LTR characters or any RTL characters, or both, whether
 * there are any explicit embedding codes, etc.
 *
 * If the (Xn) steps are performed, then the flags are re-evaluated,
 * because they will then not contain the embedding codes any more
 * and will be adjusted for override codes, so that subsequently
 * more bypassing may be possible than what the initial flags suggested.
 *
 * If the text is not mixed-directional, then the
 * algorithm steps for the weak type resolution are not performed,
 * and all levels are set to the paragraph level.
 *
 * If there are no explicit embedding codes, then the (Xn) steps
 * are not performed.
 *
 * If embedding levels are supplied as a parameter, then all
 * explicit embedding codes are ignored, and the (Xn) steps
 * are not performed.
 *
 * White Space types could get the level of the run they belong to,
 * and are checked with a test of (flags&MASK_EMBEDDING) to
 * consider if the paragraph direction should be considered in
 * the flags variable.
 *
 * If there are no White Space types in the paragraph, then
 * (L1) is not necessary in AdjustWSLevels().
 */
nsBidi::nsBidi()
{
  Init();

  mMayAllocateText=PR_TRUE;
  mMayAllocateRuns=PR_TRUE;
}

nsBidi::~nsBidi()
{
  Free();
}

void nsBidi::Init()
{
  /* reset the object, all pointers NULL, all flags PR_FALSE, all sizes 0 */
  mLength = 0;
  mParaLevel = 0;
  mFlags = 0;
  mDirection = NSBIDI_LTR;
  mTrailingWSStart = 0;

  mDirPropsSize = 0;
  mLevelsSize = 0;
  mRunsSize = 0;
  mRunCount = -1;

  mDirProps=NULL;
  mLevels=NULL;
  mRuns=NULL;

  mDirPropsMemory=NULL;
  mLevelsMemory=NULL;
  mRunsMemory=NULL;

  mMayAllocateText=PR_FALSE;
  mMayAllocateRuns=PR_FALSE;
  
}

/*
 * We are allowed to allocate memory if aMemory==NULL or
 * aMayAllocate==PR_TRUE for each array that we need.
 * We also try to grow and shrink memory as needed if we
 * allocate it.
 *
 * Assume aSizeNeeded>0.
 * If *aMemory!=NULL, then assume *aSize>0.
 *
 * ### this realloc() may unnecessarily copy the old data,
 * which we know we don't need any more;
 * is this the best way to do this??
 */
PRBool nsBidi::GetMemory(void **aMemory, PRSize *aSize, PRBool aMayAllocate, PRSize aSizeNeeded)
{
  /* check for existing memory */
  if(*aMemory==NULL) {
    /* we need to allocate memory */
    if(!aMayAllocate) {
      return PR_FALSE;
    } else {
      *aMemory=PR_MALLOC(aSizeNeeded);
      if (*aMemory!=NULL) {
        *aSize=aSizeNeeded;
        return PR_TRUE;
      } else {
        *aSize=0;
        return PR_FALSE;
      }
    }
  } else {
    /* there is some memory, is it enough or too much? */
    if(aSizeNeeded>*aSize && !aMayAllocate) {
      /* not enough memory, and we must not allocate */
      return PR_FALSE;
    } else if(aSizeNeeded!=*aSize && aMayAllocate) {
      /* we may try to grow or shrink */
      void *memory=PR_REALLOC(*aMemory, aSizeNeeded);

      if(memory!=NULL) {
        *aMemory=memory;
        *aSize=aSizeNeeded;
        return PR_TRUE;
      } else {
        /* we failed to grow */
        return PR_FALSE;
      }
    } else {
      /* we have at least enough memory and must not allocate */
      return PR_TRUE;
    }
  }
}

void nsBidi::Free()
{
  PR_FREEIF(mDirPropsMemory);
  PR_FREEIF(mLevelsMemory);
  PR_FREEIF(mRunsMemory);
}

/* SetPara ------------------------------------------------------------ */

nsresult nsBidi::SetPara(const PRUnichar *aText, PRInt32 aLength,
                         nsBidiLevel aParaLevel, nsBidiLevel *aEmbeddingLevels)
{
  nsBidiDirection direction;

  /* check the argument values */
  if(aText==NULL ||
     ((NSBIDI_MAX_EXPLICIT_LEVEL<aParaLevel) && !IS_DEFAULT_LEVEL(aParaLevel)) ||
     aLength<-1
    ) {
    return NS_ERROR_INVALID_ARG;
  }

  if(aLength==-1) {
    aLength=nsCRT::strlen(aText);
  }

  /* initialize member data */
  mLength=aLength;
  mParaLevel=aParaLevel;
  mDirection=NSBIDI_LTR;
  mTrailingWSStart=aLength;  /* the levels[] will reflect the WS run */

  mDirProps=NULL;
  mLevels=NULL;
  mRuns=NULL;

  if(aLength==0) {
    /*
     * For an empty paragraph, create an nsBidi object with the aParaLevel and
     * the flags and the direction set but without allocating zero-length arrays.
     * There is nothing more to do.
     */
    if(IS_DEFAULT_LEVEL(aParaLevel)) {
      mParaLevel&=1;
    }
    if(aParaLevel&1) {
      mFlags=DIRPROP_FLAG(R);
      mDirection=NSBIDI_RTL;
    } else {
      mFlags=DIRPROP_FLAG(L);
      mDirection=NSBIDI_LTR;
    }

    mRunCount=0;
    return NS_OK;
  }

  mRunCount=-1;

  /*
   * Get the directional properties,
   * the flags bit-set, and
   * determine the partagraph level if necessary.
   */
  if(GETDIRPROPSMEMORY(aLength)) {
    mDirProps=mDirPropsMemory;
    GetDirProps(aText);
  } else {
    return NS_ERROR_OUT_OF_MEMORY;
  }

  /* are explicit levels specified? */
  if(aEmbeddingLevels==NULL) {
    /* no: determine explicit levels according to the (Xn) rules */\
    if(GETLEVELSMEMORY(aLength)) {
      mLevels=mLevelsMemory;
      direction=ResolveExplicitLevels();
    } else {
      return NS_ERROR_OUT_OF_MEMORY;
    }
  } else {
    /* set BN for all explicit codes, check that all levels are aParaLevel..NSBIDI_MAX_EXPLICIT_LEVEL */
    mLevels=aEmbeddingLevels;
    nsresult rv = CheckExplicitLevels(&direction);
    if(NS_FAILED(rv)) {
      return rv;
    }
  }

  /*
   * The steps after (X9) in the Bidi algorithm are performed only if
   * the paragraph text has mixed directionality!
   */
  switch(direction) {
    case NSBIDI_LTR:
      /* make sure paraLevel is even */
      mParaLevel=(mParaLevel+1)&~1;

      /* all levels are implicitly at paraLevel (important for GetLevels()) */
      mTrailingWSStart=0;
      break;
    case NSBIDI_RTL:
      /* make sure paraLevel is odd */
      mParaLevel|=1;

      /* all levels are implicitly at paraLevel (important for GetLevels()) */
      mTrailingWSStart=0;
      break;
    default:
      /*
       * If there are no external levels specified and there
       * are no significant explicit level codes in the text,
       * then we can treat the entire paragraph as one run.
       * Otherwise, we need to perform the following rules on runs of
       * the text with the same embedding levels. (X10)
       * "Significant" explicit level codes are ones that actually
       * affect non-BN characters.
       * Examples for "insignificant" ones are empty embeddings
       * LRE-PDF, LRE-RLE-PDF-PDF, etc.
       */
      if(aEmbeddingLevels==NULL && !(mFlags&DIRPROP_FLAG_MULTI_RUNS)) {
        ResolveImplicitLevels(0, aLength,
                    GET_LR_FROM_LEVEL(mParaLevel),
                    GET_LR_FROM_LEVEL(mParaLevel));
      } else {
        /* sor, eor: start and end types of same-level-run */
        nsBidiLevel *levels=mLevels;
        PRInt32 start, limit=0;
        nsBidiLevel level, nextLevel;
        DirProp sor, eor;

        /* determine the first sor and set eor to it because of the loop body (sor=eor there) */
        level=mParaLevel;
        nextLevel=levels[0];
        if(level<nextLevel) {
          eor=GET_LR_FROM_LEVEL(nextLevel);
        } else {
          eor=GET_LR_FROM_LEVEL(level);
        }

        do {
          /* determine start and limit of the run (end points just behind the run) */

          /* the values for this run's start are the same as for the previous run's end */
          sor=eor;
          start=limit;
          level=nextLevel;

          /* search for the limit of this run */
          while(++limit<aLength && levels[limit]==level) {}

          /* get the correct level of the next run */
          if(limit<aLength) {
            nextLevel=levels[limit];
          } else {
            nextLevel=mParaLevel;
          }

          /* determine eor from max(level, nextLevel); sor is last run's eor */
          if((level&~NSBIDI_LEVEL_OVERRIDE)<(nextLevel&~NSBIDI_LEVEL_OVERRIDE)) {
            eor=GET_LR_FROM_LEVEL(nextLevel);
          } else {
            eor=GET_LR_FROM_LEVEL(level);
          }

          /* if the run consists of overridden directional types, then there
          are no implicit types to be resolved */
          if(!(level&NSBIDI_LEVEL_OVERRIDE)) {
            ResolveImplicitLevels(start, limit, sor, eor);
          }
        } while(limit<aLength);
      }

      /* reset the embedding levels for some non-graphic characters (L1), (X9) */
      AdjustWSLevels();
      break;
  }

  mDirection=direction;
  return NS_OK;
}

/* perform (P2)..(P3) ------------------------------------------------------- */

/*
 * Get the directional properties for the text,
 * calculate the flags bit-set, and
 * determine the partagraph level if necessary.
 */
void nsBidi::GetDirProps(const PRUnichar *aText)
{
  DirProp *dirProps=mDirPropsMemory;    /* mDirProps is const */

  PRInt32 i=0, length=mLength;
  Flags flags=0;      /* collect all directionalities in the text */
  PRUnichar uchar;
  DirProp dirProp;

  if(IS_DEFAULT_LEVEL(mParaLevel)) {
    /* determine the paragraph level (P2..P3) */
    for(;;) {
      uchar=aText[i];
      if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(aText[i+1])) {
        /* not a surrogate pair */
        flags|=DIRPROP_FLAG(dirProps[i]=dirProp=GetCharType((PRUint32)uchar));
      } else {
        /* a surrogate pair */
        dirProps[i++]=BN;   /* first surrogate in the pair gets the BN type */
        flags|=DIRPROP_FLAG(dirProps[i]=dirProp=GetCharType(GET_UTF_32(uchar, aText[i])))|DIRPROP_FLAG(BN);
      }
      ++i;
      if(dirProp==L) {
        mParaLevel=0;
        break;
      } else if(dirProp==R || dirProp==AL) {
        mParaLevel=1;
        break;
      } else if(i==length) {
        /*
         * see comment in nsIBidi.h:
         * the DEFAULT_XXX values are designed so that
         * their bit 0 alone yields the intended default
         */
        mParaLevel&=1;
        break;
      }
    }
  }

  /* get the rest of the directional properties and the flags bits */
  while(i<length) {
    uchar=aText[i];
    if(!IS_FIRST_SURROGATE(uchar) || i+1==length || !IS_SECOND_SURROGATE(aText[i+1])) {
      /* not a surrogate pair */
      flags|=DIRPROP_FLAG(dirProps[i]=GetCharType((PRUint32)uchar));
    } else {
      /* a surrogate pair */
      dirProps[i++]=BN;   /* second surrogate in the pair gets the BN type */
      flags|=DIRPROP_FLAG(dirProps[i]=GetCharType(GET_UTF_32(uchar, aText[i])))|DIRPROP_FLAG(BN);
    }
    ++i;
  }
  if(flags&MASK_EMBEDDING) {
    flags|=DIRPROP_FLAG_LR(mParaLevel);
  }
  mFlags=flags;
}

/* perform (X1)..(X9) ------------------------------------------------------- */

/*
 * Resolve the explicit levels as specified by explicit embedding codes.
 * Recalculate the flags to have them reflect the real properties
 * after taking the explicit embeddings into account.
 *
 * The Bidi algorithm is designed to result in the same behavior whether embedding
 * levels are externally specified (from "styled text", supposedly the preferred
 * method) or set by explicit embedding codes (LRx, RLx, PDF) in the plain text.
 * That is why (X9) instructs to remove all explicit codes (and BN).
 * However, in a real implementation, this removal of these codes and their index
 * positions in the plain text is undesirable since it would result in
 * reallocated, reindexed text.
 * Instead, this implementation leaves the codes in there and just ignores them
 * in the subsequent processing.
 * In order to get the same reordering behavior, positions with a BN or an
 * explicit embedding code just get the same level assigned as the last "real"
 * character.
 *
 * Some implementations, not this one, then overwrite some of these
 * directionality properties at "real" same-level-run boundaries by
 * L or R codes so that the resolution of weak types can be performed on the
 * entire paragraph at once instead of having to parse it once more and
 * perform that resolution on same-level-runs.
 * This limits the scope of the implicit rules in effectively
 * the same way as the run limits.
 *
 * Instead, this implementation does not modify these codes.
 * On one hand, the paragraph has to be scanned for same-level-runs, but
 * on the other hand, this saves another loop to reset these codes,
 * or saves making and modifying a copy of dirProps[].
 *
 *
 * Note that (Pn) and (Xn) changed significantly from version 4 of the Bidi algorithm.
 *
 *
 * Handling the stack of explicit levels (Xn):
 *
 * With the Bidi stack of explicit levels,
 * as pushed with each LRE, RLE, LRO, and RLO and popped with each PDF,
 * the explicit level must never exceed NSBIDI_MAX_EXPLICIT_LEVEL==61.
 *
 * In order to have a correct push-pop semantics even in the case of overflows,
 * there are two overflow counters:
 * - countOver60 is incremented with each LRx at level 60
 * - from level 60, one RLx increases the level to 61
 * - countOver61 is incremented with each LRx and RLx at level 61
 *
 * Popping levels with PDF must work in the opposite order so that level 61
 * is correct at the correct point. Underflows (too many PDFs) must be checked.
 *
 * This implementation assumes that NSBIDI_MAX_EXPLICIT_LEVEL is odd.
 */

nsBidiDirection nsBidi::ResolveExplicitLevels()
{
  const DirProp *dirProps=mDirProps;
  nsBidiLevel *levels=mLevels;

  PRInt32 i=0, length=mLength;
  Flags flags=mFlags;       /* collect all directionalities in the text */
  DirProp dirProp;
  nsBidiLevel level=mParaLevel;

  nsBidiDirection direction;

  /* determine if the text is mixed-directional or single-directional */
  direction=DirectionFromFlags(flags);

  /* we may not need to resolve any explicit levels */
  if(direction!=NSBIDI_MIXED) {
    /* not mixed directionality: levels don't matter - trailingWSStart will be 0 */
  } else if(!(flags&MASK_EXPLICIT)) {
    /* mixed, but all characters are at the same embedding level */
    /* set all levels to the paragraph level */
    for(i=0; i<length; ++i) {
      levels[i]=level;
    }
  } else {
    /* continue to perform (Xn) */

    /* (X1) level is set for all codes, embeddingLevel keeps track of the push/pop operations */
    /* both variables may carry the NSBIDI_LEVEL_OVERRIDE flag to indicate the override status */
    nsBidiLevel embeddingLevel=level, newLevel, stackTop=0;

    nsBidiLevel stack[NSBIDI_MAX_EXPLICIT_LEVEL];        /* we never push anything >=NSBIDI_MAX_EXPLICIT_LEVEL */
    PRUint32 countOver60=0, countOver61=0;  /* count overflows of explicit levels */

    /* recalculate the flags */
    flags=0;

    /* since we assume that this is a single paragraph, we ignore (X8) */
    for(i=0; i<length; ++i) {
      dirProp=dirProps[i];
      switch(dirProp) {
        case LRE:
        case LRO:
          /* (X3, X5) */
          newLevel=(embeddingLevel+2)&~(NSBIDI_LEVEL_OVERRIDE|1);    /* least greater even level */
          if(newLevel<=NSBIDI_MAX_EXPLICIT_LEVEL) {
            stack[stackTop]=embeddingLevel;
            ++stackTop;
            embeddingLevel=newLevel;
            if(dirProp==LRO) {
              embeddingLevel|=NSBIDI_LEVEL_OVERRIDE;
            } else {
              embeddingLevel&=~NSBIDI_LEVEL_OVERRIDE;
            }
          } else if((embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)==NSBIDI_MAX_EXPLICIT_LEVEL) {
            ++countOver61;
          } else /* (embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)==NSBIDI_MAX_EXPLICIT_LEVEL-1 */ {
            ++countOver60;
          }
          flags|=DIRPROP_FLAG(BN);
          break;
        case RLE:
        case RLO:
          /* (X2, X4) */
          newLevel=((embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)+1)|1;    /* least greater odd level */
          if(newLevel<=NSBIDI_MAX_EXPLICIT_LEVEL) {
            stack[stackTop]=embeddingLevel;
            ++stackTop;
            embeddingLevel=newLevel;
            if(dirProp==RLO) {
              embeddingLevel|=NSBIDI_LEVEL_OVERRIDE;
            } else {
              embeddingLevel&=~NSBIDI_LEVEL_OVERRIDE;
            }
          } else {
            ++countOver61;
          }
          flags|=DIRPROP_FLAG(BN);
          break;
        case PDF:
          /* (X7) */
          /* handle all the overflow cases first */
          if(countOver61>0) {
            --countOver61;
          } else if(countOver60>0 && (embeddingLevel&~NSBIDI_LEVEL_OVERRIDE)!=NSBIDI_MAX_EXPLICIT_LEVEL) {
            /* handle LRx overflows from level 60 */
            --countOver60;
          } else if(stackTop>0) {
            /* this is the pop operation; it also pops level 61 while countOver60>0 */
            --stackTop;
            embeddingLevel=stack[stackTop];
            /* } else { (underflow) */
          }
          flags|=DIRPROP_FLAG(BN);
          break;
        case B:
          /*
           * We do not really expect to see a paragraph separator (B),
           * but we should do something reasonable with it,
           * especially at the end of the text.
           */
          stackTop=0;
          countOver60=countOver61=0;
          embeddingLevel=level=mParaLevel;
          flags|=DIRPROP_FLAG(B);
          break;
        case BN:
          /* BN, LRE, RLE, and PDF are supposed to be removed (X9) */
          /* they will get their levels set correctly in AdjustWSLevels() */
          flags|=DIRPROP_FLAG(BN);
          break;
        default:
          /* all other types get the "real" level */
          if(level!=embeddingLevel) {
            level=embeddingLevel;
            if(level&NSBIDI_LEVEL_OVERRIDE) {
              flags|=DIRPROP_FLAG_O(level)|DIRPROP_FLAG_MULTI_RUNS;
            } else {
              flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG_MULTI_RUNS;
            }
          }
          if(!(level&NSBIDI_LEVEL_OVERRIDE)) {
            flags|=DIRPROP_FLAG(dirProp);
          }
          break;
      }

      /*
       * We need to set reasonable levels even on BN codes and
       * explicit codes because we will later look at same-level runs (X10).
       */
      levels[i]=level;
    }
    if(flags&MASK_EMBEDDING) {
      flags|=DIRPROP_FLAG_LR(mParaLevel);
    }

    /* subsequently, ignore the explicit codes and BN (X9) */

    /* again, determine if the text is mixed-directional or single-directional */
    mFlags=flags;
    direction=DirectionFromFlags(flags);
  }
  return direction;
}

/*
 * Use a pre-specified embedding levels array:
 *
 * Adjust the directional properties for overrides (->LEVEL_OVERRIDE),
 * ignore all explicit codes (X9),
 * and check all the preset levels.
 *
 * Recalculate the flags to have them reflect the real properties
 * after taking the explicit embeddings into account.
 */
nsresult nsBidi::CheckExplicitLevels(nsBidiDirection *aDirection)
{
  const DirProp *dirProps=mDirProps;
  nsBidiLevel *levels=mLevels;

  PRInt32 i, length=mLength;
  Flags flags=0;  /* collect all directionalities in the text */
  nsBidiLevel level, paraLevel=mParaLevel;

  for(i=0; i<length; ++i) {
    level=levels[i];
    if(level&NSBIDI_LEVEL_OVERRIDE) {
      /* keep the override flag in levels[i] but adjust the flags */
      level&=~NSBIDI_LEVEL_OVERRIDE;     /* make the range check below simpler */
      flags|=DIRPROP_FLAG_O(level);
    } else {
      /* set the flags */
      flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG(dirProps[i]);
    }
    if(level<paraLevel || NSBIDI_MAX_EXPLICIT_LEVEL<level) {
      /* level out of bounds */
      *aDirection = NSBIDI_LTR;
      return NS_ERROR_INVALID_ARG;
    }
  }
  if(flags&MASK_EMBEDDING) {
    flags|=DIRPROP_FLAG_LR(mParaLevel);
  }

  /* determine if the text is mixed-directional or single-directional */
  mFlags=flags;
  *aDirection = DirectionFromFlags(flags);
  return NS_OK;
}

/* determine if the text is mixed-directional or single-directional */
nsBidiDirection nsBidi::DirectionFromFlags(Flags aFlags)
{
  /* if the text contains AN and neutrals, then some neutrals may become RTL */
  if(!(aFlags&MASK_RTL || (aFlags&DIRPROP_FLAG(AN) && aFlags&MASK_POSSIBLE_N))) {
    return NSBIDI_LTR;
  } else if(!(aFlags&MASK_LTR)) {
    return NSBIDI_RTL;
  } else {
    return NSBIDI_MIXED;
  }
}

/* perform rules (Wn), (Nn), and (In) on a run of the text ------------------ */

/*
 * This implementation of the (Wn) rules applies all rules in one pass.
 * In order to do so, it needs a look-ahead of typically 1 character
 * (except for W5: sequences of ET) and keeps track of changes
 * in a rule Wp that affect a later Wq (p<q).
 *
 * historyOfEN is a variable-saver: it contains 4 boolean states;
 * a bit in it set to 1 means:
 *  bit 0: the current code is an EN after W2
 *  bit 1: the current code is an EN after W4
 *  bit 2: the previous code was an EN after W2
 *  bit 3: the previous code was an EN after W4
 * In other words, b0..1 have transitions of EN in the current iteration,
 * while b2..3 have the transitions of EN in the previous iteration.
 * A simple historyOfEN<<=2 suffices for the propagation.
 *
 * The (Nn) and (In) rules are also performed in that same single loop,
 * but effectively one iteration behind for white space.
 *
 * Since all implicit rules are performed in one step, it is not necessary
 * to actually store the intermediate directional properties in dirProps[].
 */

#define EN_SHIFT 2
#define EN_AFTER_W2 1
#define EN_AFTER_W4 2
#define EN_ALL 3
#define PREV_EN_AFTER_W2 4
#define PREV_EN_AFTER_W4 8

void nsBidi::ResolveImplicitLevels(PRInt32 aStart, PRInt32 aLimit,
                   DirProp aSOR, DirProp aEOR)
{
  const DirProp *dirProps=mDirProps;
  nsBidiLevel *levels=mLevels;

  PRInt32 i, next, neutralStart=-1;
  DirProp prevDirProp, dirProp, nextDirProp, lastStrong, beforeNeutral;
  PRUint8 historyOfEN;

  /* initialize: current at aSOR, next at aStart (it is aStart<aLimit) */
  next=aStart;
  beforeNeutral=dirProp=lastStrong=aSOR;
  nextDirProp=dirProps[next];
  historyOfEN=0;

  /*
   * In all steps of this implementation, BN and explicit embedding codes
   * must be treated as if they didn't exist (X9).
   * They will get levels set before a non-neutral character, and remain
   * undefined before a neutral one, but AdjustWSLevels() will take care
   * of all of them.
   */
  while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT) {
    if(++next<aLimit) {
      nextDirProp=dirProps[next];
    } else {
      nextDirProp=aEOR;
      break;
    }
  }

  /* loop for entire run */
  while(next<aLimit) {
    /* advance */
    prevDirProp=dirProp;
    dirProp=nextDirProp;
    i=next;
    do {
      if(++next<aLimit) {
        nextDirProp=dirProps[next];
      } else {
        nextDirProp=aEOR;
        break;
      }
    } while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT);
    historyOfEN<<=EN_SHIFT;

    /* (W1..W7) */
    switch(dirProp) {
      case L:
        lastStrong=L;
        break;
      case R:
        lastStrong=R;
        break;
      case AL:
        /* (W3) */
        lastStrong=AL;
        dirProp=R;
        break;
      case EN:
        /* we have to set historyOfEN correctly */
        if(lastStrong==AL) {
          /* (W2) */
          dirProp=AN;
        } else {
          if(lastStrong==L) {
            /* (W7) */
            dirProp=L;
          }
          /* this EN stays after (W2) and (W4) - at least before (W7) */
          historyOfEN|=EN_ALL;
        }
        break;
      case ES:
        if( historyOfEN&PREV_EN_AFTER_W2 &&     /* previous was EN before (W4) */
            nextDirProp==EN && lastStrong!=AL   /* next is EN and (W2) won't make it AN */
          ) {
          /* (W4) */
          if(lastStrong!=L) {
            dirProp=EN;
          } else {
            /* (W7) */
            dirProp=L;
          }
          historyOfEN|=EN_AFTER_W4;
        } else {
          /* (W6) */
          dirProp=O_N;
        }
        break;
      case CS:
        if( historyOfEN&PREV_EN_AFTER_W2 &&     /* previous was EN before (W4) */
            nextDirProp==EN && lastStrong!=AL   /* next is EN and (W2) won't make it AN */
          ) {
          /* (W4) */
          if(lastStrong!=L) {
            dirProp=EN;
          } else {
            /* (W7) */
            dirProp=L;
          }
          historyOfEN|=EN_AFTER_W4;
        } else if(prevDirProp==AN &&                    /* previous was AN */
              (nextDirProp==AN ||                   /* next is AN */
               (nextDirProp==EN && lastStrong==AL))   /* or (W2) will make it one */
             ) {
          /* (W4) */
          dirProp=AN;
        } else {
          /* (W6) */
          dirProp=O_N;
        }
        break;
      case ET:
        /* get sequence of ET; advance only next, not current, previous or historyOfEN */
        while(next<aLimit && DIRPROP_FLAG(nextDirProp)&MASK_ET_NSM_BN /* (W1), (X9) */) {
          if(++next<aLimit) {
            nextDirProp=dirProps[next];
          } else {
            nextDirProp=aEOR;
            break;
          }
        }

        if( historyOfEN&PREV_EN_AFTER_W4 ||     /* previous was EN before (W5) */
            (nextDirProp==EN && lastStrong!=AL)   /* next is EN and (W2) won't make it AN */
          ) {
          /* (W5) */
          if(lastStrong!=L) {
            dirProp=EN;
          } else {
            /* (W7) */
            dirProp=L;
          }
        } else {
          /* (W6) */
          dirProp=O_N;
        }

        /* apply the result of (W1), (W5)..(W7) to the entire sequence of ET */
        break;
      case NSM:
        /* (W1) */
        dirProp=prevDirProp;
        /* set historyOfEN back to prevDirProp's historyOfEN */
        historyOfEN>>=EN_SHIFT;
        /*
         * Technically, this should be done before the switch() in the form
         *      if(nextDirProp==NSM) {
         *          dirProps[next]=nextDirProp=dirProp;
         *      }
         *
         * - effectively one iteration ahead.
         * However, whether the next dirProp is NSM or is equal to the current dirProp
         * does not change the outcome of any condition in (W2)..(W7).
         */
        break;
      default:
        break;
    }

    /* here, it is always [prev,this,next]dirProp!=BN; it may be next>i+1 */

    /* perform (Nn) - here, only L, R, EN, AN, and neutrals are left */
    /* this is one iteration late for the neutrals */
    if(DIRPROP_FLAG(dirProp)&MASK_N) {
      if(neutralStart<0) {
        /* start of a sequence of neutrals */
        neutralStart=i;
        beforeNeutral=prevDirProp;
      }
    } else /* not a neutral, can be only one of { L, R, EN, AN } */ {
      /*
       * Note that all levels[] values are still the same at this
       * point because this function is called for an entire
       * same-level run.
       * Therefore, we need to read only one actual level.
       */
      nsBidiLevel level=levels[i];

      if(neutralStart>=0) {
        nsBidiLevel final;
        /* end of a sequence of neutrals (dirProp is "afterNeutral") */
        if(beforeNeutral==L) {
          if(dirProp==L) {
            final=0;                /* make all neutrals L (N1) */
          } else {
            final=level;            /* make all neutrals "e" (N2) */
          }
        } else /* beforeNeutral is one of { R, EN, AN } */ {
          if(dirProp==L) {
            final=level;            /* make all neutrals "e" (N2) */
          } else {
            final=1;                /* make all neutrals R (N1) */
          }
        }
        /* perform (In) on the sequence of neutrals */
        if((level^final)&1) {
          /* do something only if we need to _change_ the level */
          do {
            ++levels[neutralStart];
          } while(++neutralStart<i);
        }
        neutralStart=-1;
      }

      /* perform (In) on the non-neutral character */
      /*
       * in the cases of (W5), processing a sequence of ET,
       * and of (X9), skipping BN,
       * there may be multiple characters from i to <next
       * that all get (virtually) the same dirProp and (really) the same level
       */
      if(dirProp==L) {
        if(level&1) {
          ++level;
        } else {
          i=next;     /* we keep the levels */
        }
      } else if(dirProp==R) {
        if(!(level&1)) {
          ++level;
        } else {
          i=next;     /* we keep the levels */
        }
      } else /* EN or AN */ {
        level=(level+2)&~1;     /* least greater even level */
      }

      /* apply the new level to the sequence, if necessary */
      while(i<next) {
        levels[i++]=level;
      }
    }
  }

  /* perform (Nn) - here,
  the character after the neutrals is aEOR, which is either L or R */
  /* this is one iteration late for the neutrals */
  if(neutralStart>=0) {
    /*
     * Note that all levels[] values are still the same at this
     * point because this function is called for an entire
     * same-level run.
     * Therefore, we need to read only one actual level.
     */
    nsBidiLevel level=levels[neutralStart], final;

    /* end of a sequence of neutrals (aEOR is "afterNeutral") */
    if(beforeNeutral==L) {
      if(aEOR==L) {
        final=0;                /* make all neutrals L (N1) */
      } else {
        final=level;            /* make all neutrals "e" (N2) */
      }
    } else /* beforeNeutral is one of { R, EN, AN } */ {
      if(aEOR==L) {
        final=level;            /* make all neutrals "e" (N2) */
      } else {
        final=1;                /* make all neutrals R (N1) */
      }
    }
    /* perform (In) on the sequence of neutrals */
    if((level^final)&1) {
      /* do something only if we need to _change_ the level */
      do {
        ++levels[neutralStart];
      } while(++neutralStart<aLimit);
    }
  }
}

/* perform (L1) and (X9) ---------------------------------------------------- */

/*
 * Reset the embedding levels for some non-graphic characters (L1).
 * This function also sets appropriate levels for BN, and
 * explicit embedding types that are supposed to have been removed
 * from the paragraph in (X9).
 */
void nsBidi::AdjustWSLevels()
{
  const DirProp *dirProps=mDirProps;
  nsBidiLevel *levels=mLevels;
  PRInt32 i;

  if(mFlags&MASK_WS) {
    nsBidiLevel paraLevel=mParaLevel;
    Flags flag;

    i=mTrailingWSStart;
    while(i>0) {
      /* reset a sequence of WS/BN before eop and B/S to the paragraph paraLevel */
      while(i>0 && DIRPROP_FLAG(dirProps[--i])&MASK_WS) {
        levels[i]=paraLevel;
      }

      /* reset BN to the next character's paraLevel until B/S, which restarts above loop */
      /* here, i+1 is guaranteed to be <length */
      while(i>0) {
        flag=DIRPROP_FLAG(dirProps[--i]);
        if(flag&MASK_BN_EXPLICIT) {
          levels[i]=levels[i+1];
        } else if(flag&MASK_B_S) {
          levels[i]=paraLevel;
          break;
        }
      }
    }
  }

  /* now remove the NSBIDI_LEVEL_OVERRIDE flags, if any */
  /* (a separate loop can be optimized more easily by a compiler) */
  if(mFlags&MASK_OVERRIDE) {
    for(i=mTrailingWSStart; i>0;) {
      levels[--i]&=~NSBIDI_LEVEL_OVERRIDE;
    }
  }
}

nsresult nsBidi::GetDirection(nsBidiDirection* aDirection)
{
  *aDirection = mDirection;
  return NS_OK;
}
#ifdef FULL_BIDI_ENGINE

/* -------------------------------------------------------------------------- */

nsresult nsBidi::GetLength(PRInt32* aLength)
{
  *aLength = mLength;
  return NS_OK;
}

nsresult nsBidi::GetParaLevel(nsBidiLevel* aParaLevel)
{
  *aParaLevel = mParaLevel;
  return NS_OK;
}

/*
 * General remarks about the functions in this section:
 *
 * These functions deal with the aspects of potentially mixed-directional
 * text in a single paragraph or in a line of a single paragraph
 * which has already been processed according to
 * the Unicode 3.0 Bidi algorithm as defined in
 * http://www.unicode.org/unicode/reports/tr9/ , version 5,
 * also described in The Unicode Standard, Version 3.0 .
 *
 * This means that there is a nsBidi object with a levels
 * and a dirProps array.
 * paraLevel and direction are also set.
 * Only if the length of the text is zero, then levels==dirProps==NULL.
 *
 * The overall directionality of the paragraph
 * or line is used to bypass the reordering steps if possible.
 * Even purely RTL text does not need reordering there because
 * the getLogical/VisualIndex() functions can compute the
 * index on the fly in such a case.
 *
 * The implementation of the access to same-level-runs and of the reordering
 * do attempt to provide better performance and less memory usage compared to
 * a direct implementation of especially rule (L2) with an array of
 * one (32-bit) integer per text character.
 *
 * Here, the levels array is scanned as soon as necessary, and a vector of
 * same-level-runs is created. Reordering then is done on this vector.
 * For each run of text positions that were resolved to the same level,
 * only 8 bytes are stored: the first text position of the run and the visual
 * position behind the run after reordering.
 * One sign bit is used to hold the directionality of the run.
 * This is inefficient if there are many very short runs. If the average run
 * length is <2, then this uses more memory.
 *
 * In a further attempt to save memory, the levels array is never changed
 * after all the resolution rules (Xn, Wn, Nn, In).
 * Many functions have to consider the field trailingWSStart:
 * if it is less than length, then there is an implicit trailing run
 * at the paraLevel,
 * which is not reflected in the levels array.
 * This allows a line nsBidi object to use the same levels array as
 * its paragraph parent object.
 *
 * When a nsBidi object is created for a line of a paragraph, then the
 * paragraph's levels and dirProps arrays are reused by way of setting
 * a pointer into them, not by copying. This again saves memory and forbids to
 * change the now shared levels for (L1).
 */
nsresult nsBidi::SetLine(nsIBidi* aParaBidi, PRInt32 aStart, PRInt32 aLimit)
{
  nsBidi* pParent = (nsBidi*)aParaBidi;
  PRInt32 length;

  /* check the argument values */
  if(pParent==NULL) {
    return NS_ERROR_INVALID_POINTER;
  } else if(aStart<0 || aStart>aLimit || aLimit>pParent->mLength) {
    return NS_ERROR_INVALID_ARG;
  }

  /* set members from our aParaBidi parent */
  length=mLength=aLimit-aStart;
  mParaLevel=pParent->mParaLevel;

  mRuns=NULL;
  mFlags=0;

  if(length>0) {
    mDirProps=pParent->mDirProps+aStart;
    mLevels=pParent->mLevels+aStart;
    mRunCount=-1;

    if(pParent->mDirection!=NSBIDI_MIXED) {
      /* the parent is already trivial */
      mDirection=pParent->mDirection;

      /*
       * The parent's levels are all either
       * implicitly or explicitly ==paraLevel;
       * do the same here.
       */
      if(pParent->mTrailingWSStart<=aStart) {
        mTrailingWSStart=0;
      } else if(pParent->mTrailingWSStart<aLimit) {
        mTrailingWSStart=pParent->mTrailingWSStart-aStart;
      } else {
        mTrailingWSStart=length;
      }
    } else {
      const nsBidiLevel *levels=mLevels;
      PRInt32 i, trailingWSStart;
      nsBidiLevel level;
      Flags flags=0;

      SetTrailingWSStart();
      trailingWSStart=mTrailingWSStart;

      /* recalculate pLineBidi->direction */
      if(trailingWSStart==0) {
        /* all levels are at paraLevel */
        mDirection=(nsBidiDirection)(mParaLevel&1);
      } else {
        /* get the level of the first character */
        level=levels[0]&1;

        /* if there is anything of a different level, then the line is mixed */
        if(trailingWSStart<length && (mParaLevel&1)!=level) {
          /* the trailing WS is at paraLevel, which differs from levels[0] */
          mDirection=NSBIDI_MIXED;
        } else {
          /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
          i=1;
          for(;;) {
            if(i==trailingWSStart) {
              /* the direction values match those in level */
              mDirection=(nsBidiDirection)level;
              break;
            } else if((levels[i]&1)!=level) {
              mDirection=NSBIDI_MIXED;
              break;
            }
            ++i;
          }
        }
      }

      switch(mDirection) {
        case NSBIDI_LTR:
          /* make sure paraLevel is even */
          mParaLevel=(mParaLevel+1)&~1;

          /* all levels are implicitly at paraLevel (important for GetLevels()) */
          mTrailingWSStart=0;
          break;
        case NSBIDI_RTL:
          /* make sure paraLevel is odd */
          mParaLevel|=1;

          /* all levels are implicitly at paraLevel (important for GetLevels()) */
          mTrailingWSStart=0;
          break;
        default:
          break;
      }
    }
  } else {
    /* create an object for a zero-length line */
    mDirection=mParaLevel&1 ? NSBIDI_RTL : NSBIDI_LTR;
    mTrailingWSStart=mRunCount=0;

    mDirProps=NULL;
    mLevels=NULL;
  }
  return NS_OK;
}

/* handle trailing WS (L1) -------------------------------------------------- */

/*
 * SetTrailingWSStart() sets the start index for a trailing
 * run of WS in the line. This is necessary because we do not modify
 * the paragraph's levels array that we just point into.
 * Using trailingWSStart is another form of performing (L1).
 *
 * To make subsequent operations easier, we also include the run
 * before the WS if it is at the paraLevel - we merge the two here.
 */
void nsBidi::SetTrailingWSStart() {
  /* mDirection!=NSBIDI_MIXED */

  const DirProp *dirProps=mDirProps;
  nsBidiLevel *levels=mLevels;
  PRInt32 start=mLength;
  nsBidiLevel paraLevel=mParaLevel;

  /* go backwards across all WS, BN, explicit codes */
  while(start>0 && DIRPROP_FLAG(dirProps[start-1])&MASK_WS) {
    --start;
  }

  /* if the WS run can be merged with the previous run then do so here */
  while(start>0 && levels[start-1]==paraLevel) {
    --start;
  }

  mTrailingWSStart=start;
}

nsresult nsBidi::GetLevelAt(PRInt32 aCharIndex, nsBidiLevel* aLevel)
{
  /* return paraLevel if in the trailing WS run, otherwise the real level */
  if(aCharIndex<0 || mLength<=aCharIndex) {
    *aLevel = 0;
  } else if(mDirection!=NSBIDI_MIXED || aCharIndex>=mTrailingWSStart) {
    *aLevel = mParaLevel;
  } else {
    *aLevel = mLevels[aCharIndex];
  }
  return NS_OK;
}

nsresult nsBidi::GetLevels(nsBidiLevel** aLevels)
{
  PRInt32 start, length;

  length = mLength;
  if(length<=0) {
    *aLevels = NULL;
    return NS_ERROR_INVALID_ARG;
  }

  start = mTrailingWSStart;
  if(start==length) {
    /* the current levels array reflects the WS run */
    *aLevels = mLevels;
    return NS_OK;
  }

  /*
   * After the previous if(), we know that the levels array
   * has an implicit trailing WS run and therefore does not fully
   * reflect itself all the levels.
   * This must be a nsBidi object for a line, and
   * we need to create a new levels array.
   */

  if(GETLEVELSMEMORY(length)) {
    nsBidiLevel *levels=mLevelsMemory;

    if(start>0 && levels!=mLevels) {
      memcpy(levels, mLevels, start);
    }
    memset(levels+start, mParaLevel, length-start);

    /* this new levels array is set for the line and reflects the WS run */
    mTrailingWSStart=length;
    *aLevels=mLevels=levels;
    return NS_OK;
  } else {
    /* out of memory */
    *aLevels = NULL;
    return NS_ERROR_OUT_OF_MEMORY;
  }
}
#endif // FULL_BIDI_ENGINE

nsresult nsBidi::GetCharTypeAt(PRInt32 aCharIndex, nsCharType* pType)
{
  if(aCharIndex<0 || mLength<=aCharIndex) {
    return NS_ERROR_INVALID_ARG;
  }
  *pType = (nsCharType)mDirProps[aCharIndex];
  return NS_OK;
}

nsresult nsBidi::GetLogicalRun(PRInt32 aLogicalStart, PRInt32 *aLogicalLimit, nsBidiLevel *aLevel)
{
  PRInt32 length = mLength;

  if(aLogicalStart<0 || length<=aLogicalStart) {
    return NS_ERROR_INVALID_ARG;
  }

  if(mDirection!=NSBIDI_MIXED || aLogicalStart>=mTrailingWSStart) {
    if(aLogicalLimit!=NULL) {
      *aLogicalLimit=length;
    }
    if(aLevel!=NULL) {
      *aLevel=mParaLevel;
    }
  } else {
    nsBidiLevel *levels=mLevels;
    nsBidiLevel level=levels[aLogicalStart];

    /* search for the end of the run */
    length=mTrailingWSStart;
    while(++aLogicalStart<length && level==levels[aLogicalStart]) {}

    if(aLogicalLimit!=NULL) {
      *aLogicalLimit=aLogicalStart;
    }
    if(aLevel!=NULL) {
      *aLevel=level;
    }
  }
  return NS_OK;
}

/* runs API functions ------------------------------------------------------- */

nsresult nsBidi::CountRuns(PRInt32* aRunCount)
{
  if(mRunCount<0 && !GetRuns()) {
    return NS_ERROR_OUT_OF_MEMORY;
  } else {
    if (aRunCount)
      *aRunCount = mRunCount;
    return NS_OK;
  }
}

nsresult nsBidi::GetVisualRun(PRInt32 aRunIndex, PRInt32 *aLogicalStart, PRInt32 *aLength, nsBidiDirection *aDirection)
{
  if( aRunIndex<0 ||
      (mRunCount==-1 && !GetRuns()) ||
      aRunIndex>=mRunCount
    ) {
    *aDirection = NSBIDI_LTR;
    return NS_OK;
  } else {
    PRInt32 start=mRuns[aRunIndex].logicalStart;
    if(aLogicalStart!=NULL) {
      *aLogicalStart=GET_INDEX(start);
    }
    if(aLength!=NULL) {
      if(aRunIndex>0) {
        *aLength=mRuns[aRunIndex].visualLimit-
             mRuns[aRunIndex-1].visualLimit;
      } else {
        *aLength=mRuns[0].visualLimit;
      }
    }
    *aDirection = (nsBidiDirection)GET_ODD_BIT(start);
    return NS_OK;
  }
}

/* compute the runs array --------------------------------------------------- */

/*
 * Compute the runs array from the levels array.
 * After GetRuns() returns PR_TRUE, runCount is guaranteed to be >0
 * and the runs are reordered.
 * Odd-level runs have visualStart on their visual right edge and
 * they progress visually to the left.
 */
PRBool nsBidi::GetRuns()
{
  if(mDirection!=NSBIDI_MIXED) {
    /* simple, single-run case - this covers length==0 */
    GetSingleRun(mParaLevel);
  } else /* NSBIDI_MIXED, length>0 */ {
    /* mixed directionality */
    PRInt32 length=mLength, limit=length;

    /*
     * If there are WS characters at the end of the line
     * and the run preceding them has a level different from
     * paraLevel, then they will form their own run at paraLevel (L1).
     * Count them separately.
     * We need some special treatment for this in order to not
     * modify the levels array which a line nsBidi object shares
     * with its paragraph parent and its other line siblings.
     * In other words, for the trailing WS, it may be
     * levels[]!=paraLevel but we have to treat it like it were so.
     */
    limit=mTrailingWSStart;
    if(limit==0) {
      /* there is only WS on this line */
      GetSingleRun(mParaLevel);
    } else {
      nsBidiLevel *levels=mLevels;
      PRInt32 i, runCount;
      nsBidiLevel level=NSBIDI_DEFAULT_LTR;   /* initialize with no valid level */

      /* count the runs, there is at least one non-WS run, and limit>0 */
      runCount=0;
      for(i=0; i<limit; ++i) {
        /* increment runCount at the start of each run */
        if(levels[i]!=level) {
          ++runCount;
          level=levels[i];
        }
      }

      /*
       * We don't need to see if the last run can be merged with a trailing
       * WS run because SetTrailingWSStart() would have done that.
       */
      if(runCount==1 && limit==length) {
        /* There is only one non-WS run and no trailing WS-run. */
        GetSingleRun(levels[0]);
      } else /* runCount>1 || limit<length */ {
        /* allocate and set the runs */
        Run *runs;
        PRInt32 runIndex, start;
        nsBidiLevel minLevel=NSBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;

        /* now, count a (non-mergable) WS run */
        if(limit<length) {
          ++runCount;
        }

        /* runCount>1 */
        if(GETRUNSMEMORY(runCount)) {
          runs=mRunsMemory;
        } else {
          return PR_FALSE;
        }

        /* set the runs */
        /* this could be optimized, e.g.: 464->444, 484->444, 575->555, 595->555 */
        /* however, that would take longer and make other functions more complicated */
        runIndex=0;

        /* search for the run ends */
        start=0;
        level=levels[0];
        if(level<minLevel) {
          minLevel=level;
        }
        if(level>maxLevel) {
          maxLevel=level;
        }

        /* initialize visualLimit values with the run lengths */
        for(i=1; i<limit; ++i) {
          if(levels[i]!=level) {
            /* i is another run limit */
            runs[runIndex].logicalStart=start;
            runs[runIndex].visualLimit=i-start;
            start=i;

            level=levels[i];
            if(level<minLevel) {
              minLevel=level;
            }
            if(level>maxLevel) {
              maxLevel=level;
            }
            ++runIndex;
          }
        }

        /* finish the last run at i==limit */
        runs[runIndex].logicalStart=start;
        runs[runIndex].visualLimit=limit-start;
        ++runIndex;

        if(limit<length) {
          /* there is a separate WS run */
          runs[runIndex].logicalStart=limit;
          runs[runIndex].visualLimit=length-limit;
          if(mParaLevel<minLevel) {
            minLevel=mParaLevel;
          }
        }

        /* set the object fields */
        mRuns=runs;
        mRunCount=runCount;

        ReorderLine(minLevel, maxLevel);

        /* now add the direction flags and adjust the visualLimit's to be just that */
        ADD_ODD_BIT_FROM_LEVEL(runs[0].logicalStart, levels[runs[0].logicalStart]);
        limit=runs[0].visualLimit;
        for(i=1; i<runIndex; ++i) {
          ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
          limit=runs[i].visualLimit+=limit;
        }

        /* same for the trailing WS run */
        if(runIndex<runCount) {
          ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, mParaLevel);
          runs[runIndex].visualLimit+=limit;
        }
      }
    }
  }
  return PR_TRUE;
}

/* in trivial cases there is only one trivial run; called by GetRuns() */
void nsBidi::GetSingleRun(nsBidiLevel aLevel)
{
  /* simple, single-run case */
  mRuns=mSimpleRuns;
  mRunCount=1;

  /* fill and reorder the single run */
  mRuns[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, aLevel);
  mRuns[0].visualLimit=mLength;
}

/* reorder the runs array (L2) ---------------------------------------------- */

/*
 * Reorder the same-level runs in the runs array.
 * Here, runCount>1 and maxLevel>=minLevel>=paraLevel.
 * All the visualStart fields=logical start before reordering.
 * The "odd" bits are not set yet.
 *
 * Reordering with this data structure lends itself to some handy shortcuts:
 *
 * Since each run is moved but not modified, and since at the initial maxLevel
 * each sequence of same-level runs consists of only one run each, we
 * don't need to do anything there and can predecrement maxLevel.
 * In many simple cases, the reordering is thus done entirely in the
 * index mapping.
 * Also, reordering occurs only down to the lowest odd level that occurs,
 * which is minLevel|1. However, if the lowest level itself is odd, then
 * in the last reordering the sequence of the runs at this level or higher
 * will be all runs, and we don't need the elaborate loop to search for them.
 * This is covered by ++minLevel instead of minLevel|=1 followed
 * by an extra reorder-all after the reorder-some loop.
 * About a trailing WS run:
 * Such a run would need special treatment because its level is not
 * reflected in levels[] if this is not a paragraph object.
 * Instead, all characters from trailingWSStart on are implicitly at
 * paraLevel.
 * However, for all maxLevel>paraLevel, this run will never be reordered
 * and does not need to be taken into account. maxLevel==paraLevel is only reordered
 * if minLevel==paraLevel is odd, which is done in the extra segment.
 * This means that for the main reordering loop we don't need to consider
 * this run and can --runCount. If it is later part of the all-runs
 * reordering, then runCount is adjusted accordingly.
 */
void nsBidi::ReorderLine(nsBidiLevel aMinLevel, nsBidiLevel aMaxLevel)
{
  Run *runs;
  nsBidiLevel *levels;
  PRInt32 firstRun, endRun, limitRun, runCount, temp;

  /* nothing to do? */
  if(aMaxLevel<=(aMinLevel|1)) {
    return;
  }

  /*
   * Reorder only down to the lowest odd level
   * and reorder at an odd aMinLevel in a separate, simpler loop.
   * See comments above for why aMinLevel is always incremented.
   */
  ++aMinLevel;

  runs=mRuns;
  levels=mLevels;
  runCount=mRunCount;

  /* do not include the WS run at paraLevel<=old aMinLevel except in the simple loop */
  if(mTrailingWSStart<mLength) {
    --runCount;
  }

  while(--aMaxLevel>=aMinLevel) {
    firstRun=0;

    /* loop for all sequences of runs */
    for(;;) {
      /* look for a sequence of runs that are all at >=aMaxLevel */
      /* look for the first run of such a sequence */
      while(firstRun<runCount && levels[runs[firstRun].logicalStart]<aMaxLevel) {
        ++firstRun;
      }
      if(firstRun>=runCount) {
        break;  /* no more such runs */
      }

      /* look for the limit run of such a sequence (the run behind it) */
      for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=aMaxLevel;) {}

      /* Swap the entire sequence of runs from firstRun to limitRun-1. */
      endRun=limitRun-1;
      while(firstRun<endRun) {
        temp=runs[firstRun].logicalStart;
        runs[firstRun].logicalStart=runs[endRun].logicalStart;
        runs[endRun].logicalStart=temp;

        temp=runs[firstRun].visualLimit;
        runs[firstRun].visualLimit=runs[endRun].visualLimit;
        runs[endRun].visualLimit=temp;

        ++firstRun;
        --endRun;
      }

      if(limitRun==runCount) {
        break;  /* no more such runs */
      } else {
        firstRun=limitRun+1;
      }
    }
  }

  /* now do aMaxLevel==old aMinLevel (==odd!), see above */
  if(!(aMinLevel&1)) {
    firstRun=0;

    /* include the trailing WS run in this complete reordering */
    if(mTrailingWSStart==mLength) {
      --runCount;
    }

    /* Swap the entire sequence of all runs. (endRun==runCount) */
    while(firstRun<runCount) {
      temp=runs[firstRun].logicalStart;
      runs[firstRun].logicalStart=runs[runCount].logicalStart;
      runs[runCount].logicalStart=temp;

      temp=runs[firstRun].visualLimit;
      runs[firstRun].visualLimit=runs[runCount].visualLimit;
      runs[runCount].visualLimit=temp;

      ++firstRun;
      --runCount;
    }
  }
}

nsresult nsBidi::ReorderVisual(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap)
{
  PRInt32 start, end, limit, temp;
  nsBidiLevel minLevel, maxLevel;

  if(aIndexMap==NULL || !PrepareReorder(aLevels, aLength, aIndexMap, &minLevel, &maxLevel)) {
    return NS_OK;
  }

  /* nothing to do? */
  if(minLevel==maxLevel && (minLevel&1)==0) {
    return NS_OK;
  }

  /* reorder only down to the lowest odd level */
  minLevel|=1;

  /* loop maxLevel..minLevel */
  do {
    start=0;

    /* loop for all sequences of levels to reorder at the current maxLevel */
    for(;;) {
      /* look for a sequence of levels that are all at >=maxLevel */
      /* look for the first index of such a sequence */
      while(start<aLength && aLevels[start]<maxLevel) {
        ++start;
      }
      if(start>=aLength) {
        break;  /* no more such runs */
      }

      /* look for the limit of such a sequence (the index behind it) */
      for(limit=start; ++limit<aLength && aLevels[limit]>=maxLevel;) {}

      /*
       * Swap the entire interval of indexes from start to limit-1.
       * We don't need to swap the levels for the purpose of this
       * algorithm: the sequence of levels that we look at does not
       * move anyway.
       */
      end=limit-1;
      while(start<end) {
        temp=aIndexMap[start];
        aIndexMap[start]=aIndexMap[end];
        aIndexMap[end]=temp;

        ++start;
        --end;
      }

      if(limit==aLength) {
        break;  /* no more such sequences */
      } else {
        start=limit+1;
      }
    }
  } while(--maxLevel>=minLevel);

  return NS_OK;
}

PRBool nsBidi::PrepareReorder(const nsBidiLevel *aLevels, PRInt32 aLength,
                PRInt32 *aIndexMap,
                nsBidiLevel *aMinLevel, nsBidiLevel *aMaxLevel)
{
  PRInt32 start;
  nsBidiLevel level, minLevel, maxLevel;

  if(aLevels==NULL || aLength<=0) {
    return PR_FALSE;
  }

  /* determine minLevel and maxLevel */
  minLevel=NSBIDI_MAX_EXPLICIT_LEVEL+1;
  maxLevel=0;
  for(start=aLength; start>0;) {
    level=aLevels[--start];
    if(level>NSBIDI_MAX_EXPLICIT_LEVEL+1) {
      return PR_FALSE;
    }
    if(level<minLevel) {
      minLevel=level;
    }
    if(level>maxLevel) {
      maxLevel=level;
    }
  }
  *aMinLevel=minLevel;
  *aMaxLevel=maxLevel;

  /* initialize the index map */
  for(start=aLength; start>0;) {
    --start;
    aIndexMap[start]=start;
  }

  return PR_TRUE;
}

#ifdef FULL_BIDI_ENGINE
/* API functions for logical<->visual mapping ------------------------------- */

nsresult nsBidi::GetVisualIndex(PRInt32 aLogicalIndex, PRInt32* aVisualIndex) {
  if(aLogicalIndex<0 || mLength<=aLogicalIndex) {
    return NS_ERROR_INVALID_ARG;
  } else {
    /* we can do the trivial cases without the runs array */
    switch(mDirection) {
      case NSBIDI_LTR:
        *aVisualIndex = aLogicalIndex;
        return NS_OK;
      case NSBIDI_RTL:
        *aVisualIndex = mLength-aLogicalIndex-1;
        return NS_OK;
      default:
        if(mRunCount<0 && !GetRuns()) {
          return NS_ERROR_OUT_OF_MEMORY;
        } else {
          Run *runs=mRuns;
          PRInt32 i, visualStart=0, offset, length;

          /* linear search for the run, search on the visual runs */
          for(i=0;; ++i) {
            length=runs[i].visualLimit-visualStart;
            offset=aLogicalIndex-GET_INDEX(runs[i].logicalStart);
            if(offset>=0 && offset<length) {
              if(IS_EVEN_RUN(runs[i].logicalStart)) {
                /* LTR */
                *aVisualIndex = visualStart+offset;
                return NS_OK;
              } else {
                /* RTL */
                *aVisualIndex = visualStart+length-offset-1;
                return NS_OK;
              }
            }
            visualStart+=length;
          }
        }
    }
  }
}

nsresult nsBidi::GetLogicalIndex(PRInt32 aVisualIndex, PRInt32 *aLogicalIndex)
{
  if(aVisualIndex<0 || mLength<=aVisualIndex) {
    return NS_ERROR_INVALID_ARG;
  } else {
    /* we can do the trivial cases without the runs array */
    switch(mDirection) {
      case NSBIDI_LTR:
        *aLogicalIndex = aVisualIndex;
        return NS_OK;
      case NSBIDI_RTL:
        *aLogicalIndex = mLength-aVisualIndex-1;
        return NS_OK;
      default:
        if(mRunCount<0 && !GetRuns()) {
          return NS_ERROR_OUT_OF_MEMORY;
        } else {
          Run *runs=mRuns;
          PRInt32 i, runCount=mRunCount, start;

          if(runCount<=10) {
            /* linear search for the run */
            for(i=0; aVisualIndex>=runs[i].visualLimit; ++i) {}
          } else {
            /* binary search for the run */
            PRInt32 start=0, limit=runCount;

            /* the middle if() will guaranteed find the run, we don't need a loop limit */
            for(;;) {
              i=(start+limit)/2;
              if(aVisualIndex>=runs[i].visualLimit) {
                start=i+1;
              } else if(i==0 || aVisualIndex>=runs[i-1].visualLimit) {
                break;
              } else {
                limit=i;
              }
            }
          }

          start=runs[i].logicalStart;
          if(IS_EVEN_RUN(start)) {
            /* LTR */
            /* the offset in runs[i] is aVisualIndex-runs[i-1].visualLimit */
            if(i>0) {
              aVisualIndex-=runs[i-1].visualLimit;
            }
            *aLogicalIndex = GET_INDEX(start)+aVisualIndex;
            return NS_OK;
          } else {
            /* RTL */
            *aLogicalIndex = GET_INDEX(start)+runs[i].visualLimit-aVisualIndex-1;
            return NS_OK;
          }
        }
    }
  }
}

nsresult nsBidi::GetLogicalMap(PRInt32 *aIndexMap)
{
  nsBidiLevel *levels;
  nsresult rv;

  /* GetLevels() checks all of its and our arguments */
  rv = GetLevels(&levels);
  if(NS_FAILED(rv)) {
    return rv;
  } else if(aIndexMap==NULL) {
    return NS_ERROR_INVALID_ARG;
  } else {
    return ReorderLogical(levels, mLength, aIndexMap);
  }
}

nsresult nsBidi::GetVisualMap(PRInt32 *aIndexMap)
{
  PRInt32* runCount=NULL;
  nsresult rv;

  /* CountRuns() checks all of its and our arguments */
  rv = CountRuns(runCount);
  if(NS_FAILED(rv)) {
    return rv;
  } else if(aIndexMap==NULL) {
    return NS_ERROR_INVALID_ARG;
  } else {
    /* fill a visual-to-logical index map using the runs[] */
    Run *runs=mRuns, *runsLimit=runs+mRunCount;
    PRInt32 logicalStart, visualStart, visualLimit;

    visualStart=0;
    for(; runs<runsLimit; ++runs) {
      logicalStart=runs->logicalStart;
      visualLimit=runs->visualLimit;
      if(IS_EVEN_RUN(logicalStart)) {
        do { /* LTR */
          *aIndexMap++ = logicalStart++;
        } while(++visualStart<visualLimit);
      } else {
        REMOVE_ODD_BIT(logicalStart);
        logicalStart+=visualLimit-visualStart;  /* logicalLimit */
        do { /* RTL */
          *aIndexMap++ = --logicalStart;
        } while(++visualStart<visualLimit);
      }
      /* visualStart==visualLimit; */
    }
    return NS_OK;
  }
}

/* reorder a line based on a levels array (L2) ------------------------------ */

nsresult nsBidi::ReorderLogical(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap)
{
  PRInt32 start, limit, sumOfSosEos;
  nsBidiLevel minLevel, maxLevel;

  if(aIndexMap==NULL || !PrepareReorder(aLevels, aLength, aIndexMap, &minLevel, &maxLevel)) {
    return NS_OK;
  }

  /* nothing to do? */
  if(minLevel==maxLevel && (minLevel&1)==0) {
    return NS_OK;
  }

  /* reorder only down to the lowest odd level */
  minLevel|=1;

  /* loop maxLevel..minLevel */
  do {
    start=0;

    /* loop for all sequences of levels to reorder at the current maxLevel */
    for(;;) {
      /* look for a sequence of levels that are all at >=maxLevel */
      /* look for the first index of such a sequence */
      while(start<aLength && aLevels[start]<maxLevel) {
        ++start;
      }
      if(start>=aLength) {
        break;  /* no more such sequences */
      }

      /* look for the limit of such a sequence (the index behind it) */
      for(limit=start; ++limit<aLength && aLevels[limit]>=maxLevel;) {}

      /*
       * sos=start of sequence, eos=end of sequence
       *
       * The closed (inclusive) interval from sos to eos includes all the logical
       * and visual indexes within this sequence. They are logically and
       * visually contiguous and in the same range.
       *
       * For each run, the new visual index=sos+eos-old visual index;
       * we pre-add sos+eos into sumOfSosEos ->
       * new visual index=sumOfSosEos-old visual index;
       */
      sumOfSosEos=start+limit-1;

      /* reorder each index in the sequence */
      do {
        aIndexMap[start]=sumOfSosEos-aIndexMap[start];
      } while(++start<limit);

      /* start==limit */
      if(limit==aLength) {
        break;  /* no more such sequences */
      } else {
        start=limit+1;
      }
    }
  } while(--maxLevel>=minLevel);

  return NS_OK;
}

nsresult nsBidi::InvertMap(const PRInt32 *aSrcMap, PRInt32 *aDestMap, PRInt32 aLength)
{
  if(aSrcMap!=NULL && aDestMap!=NULL) {
    aSrcMap+=aLength;
    while(aLength>0) {
      aDestMap[*--aSrcMap]=--aLength;
    }
  }
  return NS_OK;
}

PRInt32 nsBidi::doWriteReverse(const PRUnichar *src, PRInt32 srcLength,
                               PRUnichar *dest, PRUint16 options) {
  /*
   * RTL run -
   *
   * RTL runs need to be copied to the destination in reverse order
   * of code points, not code units, to keep Unicode characters intact.
   *
   * The general strategy for this is to read the source text
   * in backward order, collect all code units for a code point
   * (and optionally following combining characters, see below),
   * and copy all these code units in ascending order
   * to the destination for this run.
   *
   * Several options request whether combining characters
   * should be kept after their base characters,
   * whether Bidi control characters should be removed, and
   * whether characters should be replaced by their mirror-image
   * equivalent Unicode characters.
   */
  PRInt32 i, j, destSize;
  PRUint32 c;

  /* optimize for several combinations of options */
  switch(options&(NSBIDI_REMOVE_BIDI_CONTROLS|NSBIDI_DO_MIRRORING|NSBIDI_KEEP_BASE_COMBINING)) {
    case 0:
    /*
         * With none of the "complicated" options set, the destination
         * run will have the same length as the source run,
         * and there is no mirroring and no keeping combining characters
         * with their base characters.
         */
      destSize=srcLength;

    /* preserve character integrity */
      do {
      /* i is always after the last code unit known to need to be kept in this segment */
        i=srcLength;

      /* collect code units for one base character */
        UTF_BACK_1(src, 0, srcLength);

      /* copy this base character */
        j=srcLength;
        do {
          *dest++=src[j++];
        } while(j<i);
      } while(srcLength>0);
      break;
    case NSBIDI_KEEP_BASE_COMBINING:
    /*
         * Here, too, the destination
         * run will have the same length as the source run,
         * and there is no mirroring.
         * We do need to keep combining characters with their base characters.
         */
      destSize=srcLength;

    /* preserve character integrity */
      do {
      /* i is always after the last code unit known to need to be kept in this segment */
        i=srcLength;

      /* collect code units and modifier letters for one base character */
        do {
          UTF_PREV_CHAR(src, 0, srcLength, c);
        } while(srcLength>0 && IsBidiCategory(c, eBidiCat_NSM));

      /* copy this "user character" */
        j=srcLength;
        do {
          *dest++=src[j++];
        } while(j<i);
      } while(srcLength>0);
      break;
    default:
    /*
         * With several "complicated" options set, this is the most
         * general and the slowest copying of an RTL run.
         * We will do mirroring, remove Bidi controls, and
         * keep combining characters with their base characters
         * as requested.
         */
      if(!(options&NSBIDI_REMOVE_BIDI_CONTROLS)) {
        i=srcLength;
      } else {
      /* we need to find out the destination length of the run,
               which will not include the Bidi control characters */
        PRInt32 length=srcLength;
        PRUnichar ch;

        i=0;
        do {
          ch=*src++;
          if (!IsBidiControl((PRUint32)ch)) {
            ++i;
          }
        } while(--length>0);
        src-=srcLength;
      }
      destSize=i;

    /* preserve character integrity */
      do {
      /* i is always after the last code unit known to need to be kept in this segment */
        i=srcLength;

      /* collect code units for one base character */
        UTF_PREV_CHAR(src, 0, srcLength, c);
        if(options&NSBIDI_KEEP_BASE_COMBINING) {
        /* collect modifier letters for this base character */
          while(srcLength>0 && IsBidiCategory(c, eBidiCat_NSM)) {
            UTF_PREV_CHAR(src, 0, srcLength, c);
          }
        }

        if(options&NSBIDI_REMOVE_BIDI_CONTROLS && IsBidiControl(c)) {
        /* do not copy this Bidi control character */
          continue;
        }

      /* copy this "user character" */
        j=srcLength;
        if(options&NSBIDI_DO_MIRRORING) {
          /* mirror only the base character */
          c = SymmSwap(c);

          PRInt32 k=0;
          UTF_APPEND_CHAR_UNSAFE(dest, k, c);
          dest+=k;
          j+=k;
        }
        while(j<i) {
          *dest++=src[j++];
        }
      } while(srcLength>0);
      break;
  } /* end of switch */
  return destSize;
}

nsresult nsBidi::WriteReverse(const PRUnichar *aSrc, PRInt32 aSrcLength, PRUnichar *aDest, PRUint16 aOptions, PRInt32 *aDestSize)
{
  if( aSrc==NULL || aSrcLength<0 ||
      aDest==NULL
    ) {
    return NS_ERROR_INVALID_ARG;
  }

  /* do input and output overlap? */
  if( aSrc>=aDest && aSrc<aDest+aSrcLength ||
      aDest>=aSrc && aDest<aSrc+aSrcLength
    ) {
    return NS_ERROR_INVALID_ARG;
  }

  if(aSrcLength>0) {
    *aDestSize = doWriteReverse(aSrc, aSrcLength, aDest, aOptions);
  }
  return NS_OK;
}
#endif // FULL_BIDI_ENGINE
#endif // IBMBIDI