content: /**
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You under the Apache License, Version 2.0
   * (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.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package org.apache.solr.util;
  
  
  /**
   * @version $Id: BCDUtils.java 555343 2007-07-11 17:46:25Z hossman $
   */
  public class BCDUtils {
    // idiv is expensive...
    // use fixed point math to multiply by 1/10
    // http://www.cs.uiowa.edu/~jones/bcd/divide.html
    private static int div10(int a) { return (a * 0xcccd) >>> 19; }
    private static int mul10(int a) { return (a*10); }
    // private static int mul10(int a) { return ((a<<3)+(a<<1)); }
    // private static int mul10(int a) { return (a+(a<<2))<<1; } // attempt to use LEA instr
    // (imul32 on AMD64 only has a 3 cycle latency in any case)
  
  
    // something that won't clash with other base100int
  // chars (something >= 100)
    private static final char NEG_CHAR=(char)126;
    // The zero exponent.
  // NOTE: for smaller integer representations, this current implementation
  // combines sign and exponent into the first char.  sign is negative if
  // exponent is less than the zero point (no negative exponents themselves)
    private static final int ZERO_EXPONENT='a';  // 97
  
    // WARNING: assumption is that this is a legal int...
  // no validation is done.  [+-]?digit*
  //
  // Normalization of zeros *is* done...
  //  0004, 004, 04, 4 will all end up being equal
  //  0,-0 are normalized to '' (zero length)
  //
  // The value is written to the output buffer
  // from the end to the start.  The return value
  // is the start of the Base100 int in the output buffer.
  //
  // As the output will be smaller than the input, arr and
  // out may refer to the same array if desired.
  //
    public static int base10toBase100(char[] arr, int start, int end,
                                      char[] out, int outend
                                      )
    {
      int wpos=outend;  // write position
      boolean neg=false;
  
      while (--end >= start) {
        int val = arr[end];
        if (val=='+') { break; }
        else if (val=='-') { neg=!neg; break; }
        else {
          val = val - '0';
          if (end > start) {
            int val2 = arr[end-1];
            if (val2=='+') { out[--wpos]=(char)val; break; }
            if (val2=='-') { out[--wpos]=(char)val; neg=!neg; break; }
            end--;
            val = val + (val2 - '0')*10;
          }
          out[--wpos] = (char)val;
        }
      }
  
      // remove leading base100 zeros
      while (wpos<outend && out[wpos]==0) wpos++;
  
      // check for a zero value
      if (wpos==outend) {
        // if zero, don't add negative sign
      } else if (neg) {
        out[--wpos]=NEG_CHAR;
      }
  
      return wpos;  // the start of the base100 int
    }
  
    // Converts a base100 number to base10 character form
  // returns number of chars written.
  // At least 1 char is always written.
    public static int base100toBase10(char[] arr, int start, int end,
                                      char[] out, int offset)
    {
      int wpos=offset;  // write position
      boolean firstDigit=true;
      for (int i=start; i<end; i++) {
        int val = arr[i];
        if (val== NEG_CHAR) { out[wpos++]='-'; continue; }
        char tens = (char)(val / 10 + '0');
        if (!firstDigit || tens!='0') {  // skip leading 0
          out[wpos++] = (char)(val / 10 + '0');    // tens position
        }
        out[wpos++] = (char)(val % 10 + '0');    // ones position
        firstDigit=false;
      }
      if (firstDigit) out[wpos++]='0';
      return wpos-offset;
    }
  
    public static String base10toBase100SortableInt(String val) {
      char[] arr = new char[val.length()+1];
      val.getChars(0,val.length(),arr,0);
      int len = base10toBase100SortableInt(arr,0,val.length(),arr,arr.length);
      return new String(arr,arr.length-len,len);
    }
  
    public static String base100SortableIntToBase10(String val) {
      int slen = val.length();
      char[] arr = new char[slen<<2];
      val.getChars(0,slen,arr,0);
      int len = base100SortableIntToBase10(arr,0,slen,arr,slen);
      return new String(arr,slen,len);
    }
  
    public static String base10toBase10kSortableInt(String val) {
      char[] arr = new char[val.length()+1];
      val.getChars(0,val.length(),arr,0);
      int len = base10toBase10kSortableInt(arr,0,val.length(),arr,arr.length);
      return new String(arr,arr.length-len,len);
    }
  
    public static String base10kSortableIntToBase10(String val) {
      int slen = val.length();
      char[] arr = new char[slen*5]; // +1 time for orig, +4 for new
      val.getChars(0,slen,arr,0);
      int len = base10kSortableIntToBase10(arr,0,slen,arr,slen);
      return new String(arr,slen,len);
    }
  
    /********* FUTURE
      // the zero exponent... exponents above this point are positive
      // and below are negative.
      // It is desirable to make ordinary numbers have a single byte
      // exponent when converted to UTF-8
      // For integers, the exponent will always be >=0, but this format
      // is meant to be valid for floating point numbers as well...
      private static final int ZERO_EXPONENT='a';  // 97
  
      // if exponent is larger than what can be represented
      // in a single byte (char), then this is the multibyte
      // escape char.
      // UCS-2 surrogates start at 0xD800
      private static final int POSITIVE_EXPONENT_ESCAPE=0x3fff;
  
      // if exponent is smaller than what can be represented in
      // a single byte, then this is the multibyte escape
      private static final int NEGATIVE_EXPONENT_ESCAPE=1;
  
      // if number is negative, it starts with this optional value
      // this should not overlap with any exponent values
      private static final int NEGATIVE_SIGN=0;
    **********/
  
      // WARNING: assumption is that this is a legal int...
      // no validation is done.  [+-]?digit*
      //
      // Normalization of zeros *is* done...
      //  0004, 004, 04, 4 will all end up being equal
      //  0,-0 are normalized to '' (zero length)
      //
      // The value is written to the output buffer
      // from the end to the start.  The return value
      // is the start of the Base100 int in the output buffer.
      //
      // As the output will be smaller than the input, arr and
      // out may refer to the same array if desired.
      //
      public static int base10toBase100SortableInt(char[] arr, int start, int end,
                                                   char[] out, int outend
                                        )
      {
        int wpos=outend;  // write position
        boolean neg=false;
        --end;  // position end pointer *on* the last char
  
        // read signs and leading zeros
        while (start <= end) {
          char val = arr[start];
          if (val=='-') neg=!neg;
          else if (val>='1' && val<='9') break;
          start++;
        }
  
        // eat whitespace on RHS?
        outer: while (start <= end) {
          switch(arr[end]) {
            case ' ':
            case '\t':
            case '\n':
            case '\r': end--; break;
            default: break outer;
          }
        }
  
        int hundreds=0;
        /******************************************************
         * remove RHS zero normalization since it only helps 1 in 100
         * numbers and complicates both encoding and decoding.
  
        // remove pairs of zeros on the RHS and keep track of
        // the count.
        while (start <= end) {
          char val = arr[end];
  
          if (val=='0' && start <= end) {
            val=arr[end-1];
            if (val=='0') {
              hundreds++;
              end-=2;
              continue;
            }
          }
  
          break;
        }
        *************************************************************/
  
  
        // now start at the end and work our way forward
        // encoding two base 10 digits into 1 base 100 digit
        while (start <= end) {
          int val = arr[end--];
          val = val - '0';
          if (start <= end) {
            int val2 = arr[end--];
            val = val + (val2 - '0')*10;
          }
          out[--wpos] = neg ? (char)(99-val) : (char)val;
        }
  
        /****** FUTURE: not needed for this implementation of exponent combined with sign
        // normalize all zeros to positive values
        if (wpos==outend) neg=false;
        ******/
  
        // adjust exponent by the number of base 100 chars written
        hundreds += outend - wpos;
  
        // write the exponent and sign combined
        out[--wpos] = neg ? (char)(ZERO_EXPONENT - hundreds) : (char)(ZERO_EXPONENT + hundreds);
  
        return outend-wpos;  // the length of the base100 int
      }
  
    // Converts a base100 sortable number to base10 character form
  // returns number of chars written.
  // At least 1 char is always written.
    public static int base100SortableIntToBase10(char[] arr, int start, int end,
                                                 char[] out, int offset)
    {
      // Take care of "0" case first.  It's the only number that is represented
      // in one char.
      if (end-start == 1) {
        out[offset]='0';
        return 1;
      }
  
      int wpos = offset;  // write position
      boolean neg = false;
      int exp = arr[start++];
      if (exp < ZERO_EXPONENT) {
        neg=true;
        exp = ZERO_EXPONENT - exp;
        out[wpos++]='-';
      }
  
      boolean firstDigit=true;
      while (start < end) {
        int val = arr[start++];
        if (neg) val = 99 - val;
        // opt - if we ever want a faster version we can avoid one integer
        // divide by using fixed point math to multiply by 1/10
        // http://www.cs.uiowa.edu/~jones/bcd/divide.html
        // TIP: write a small function in gcc or cl and see what
        // the optimized assemply output looks like (and which is fastest).
        // In C you can specify "unsigned" which gives the compiler more
        // info than the Java compiler has.
        char tens = (char)(val / 10 + '0');
        if (!firstDigit || tens!='0') {  // skip leading 0
          out[wpos++] = tens;      // write tens position
        }
        out[wpos++] = (char)(val % 10 + '0');    // write ones position
        firstDigit=false;
      }
  
      // OPTIONAL: if trailing zeros were truncated, then this is where
      // we would restore them (compare number of chars read vs exponent)
  
      return wpos-offset;
    }
  
    public static int base10toBase10kSortableInt(char[] arr, int start, int end,
                                                 char[] out, int outend
                                      )
    {
      int wpos=outend;  // write position
      boolean neg=false;
      --end;  // position end pointer *on* the last char
  
      // read signs and leading zeros
      while (start <= end) {
        char val = arr[start];
        if (val=='-') neg=!neg;
        else if (val>='1' && val<='9') break;
        start++;
      }
  
      // eat whitespace on RHS?
      outer: while (start <= end) {
        switch(arr[end]) {
          case ' ': // fallthrough
          case '\t': // fallthrough
          case '\n': // fallthrough
          case '\r': end--; break;
          default: break outer;
        }
      }
  
      int exp=0;
  
      /******************************************************
       * remove RHS zero normalization since it only helps 1 in 100
       * numbers and complicates both encoding and decoding.
  
      // remove pairs of zeros on the RHS and keep track of
      // the count.
      while (start <= end) {
        char val = arr[end];
  
        if (val=='0' && start <= end) {
          val=arr[end-1];
          if (val=='0') {
            hundreds++;
            end-=2;
            continue;
          }
        }
  
        break;
      }
      *************************************************************/
  
  
      // now start at the end and work our way forward
      // encoding two base 10 digits into 1 base 100 digit
      while (start <= end) {
        int val = arr[end--] - '0';          // ones
        if (start <= end) {
          val += (arr[end--] - '0')*10;      // tens
          if (start <= end) {
            val += (arr[end--] - '0')*100;    // hundreds
            if (start <= end) {
              val += (arr[end--] - '0')*1000;  // thousands
            }
          }
        }
        out[--wpos] = neg ? (char)(9999-val) : (char)val;
      }
  
  
      /****** FUTURE: not needed for this implementation of exponent combined with sign
      // normalize all zeros to positive values
      if (wpos==outend) neg=false;
      ******/
  
      // adjust exponent by the number of base 100 chars written
      exp += outend - wpos;
  
      // write the exponent and sign combined
      out[--wpos] = neg ? (char)(ZERO_EXPONENT - exp) : (char)(ZERO_EXPONENT + exp);
  
      return outend-wpos;  // the length of the base100 int
    }
  
    // Converts a base100 sortable number to base10 character form
  // returns number of chars written.
  // At least 1 char is always written.
    public static int base10kSortableIntToBase10(char[] arr, int start, int end,
                                                 char[] out, int offset)
    {
      // Take care of "0" case first.  It's the only number that is represented
      // in one char since we don't chop trailing zeros.
      if (end-start == 1) {
        out[offset]='0';
        return 1;
      }
  
      int wpos = offset;  // write position
      boolean neg;
      int exp = arr[start++];
      if (exp < ZERO_EXPONENT) {
        neg=true;
        // We don't currently use exp on decoding...
        // exp = ZERO_EXPONENT - exp;
        out[wpos++]='-';
      } else {
        neg=false;
      }
  
      // since so many values will fall in one char, pull it
      // out of the loop (esp since the first value must
      // be special-cased to not print leading zeros.
      // integer division is still expensive, so it's best to check
      // if you actually need to do it.
      //
      // TIP: write a small function in gcc or cl and see what
      // the optimized assemply output looks like (and which is fastest).
      // In C you can specify "unsigned" which gives the compiler more
      // info than the Java compiler has.
      int val = arr[start++];
      if (neg) val = 9999 - val;
  
      /***
      if (val < 10) {
        out[wpos++] = (char)(val + '0');
      } else if (val < 100) {
        out[wpos++] = (char)(val/10 + '0');
        out[wpos++] = (char)(val%10 + '0');
      } else if (val < 1000) {
        out[wpos++] = (char)(val/100 + '0');
        out[wpos++] = (char)((val/10)%10 + '0');
        out[wpos++] = (char)(val%10 + '0');
      } else {
        out[wpos++] = (char)(val/1000 + '0');
        out[wpos++] = (char)((val/100)%10 + '0');
        out[wpos++] = (char)((val/10)%10 + '0');
        out[wpos++] = (char)(val % 10 + '0');
      }
      ***/
  
      if (val < 10) {
        out[wpos++] = (char)(val + '0');
      } else if (val < 100) {
        int div = div10(val);
        int ones = val - mul10(div); // mod 10
        out[wpos++] = (char)(div + '0');
        out[wpos++] = (char)(ones + '0');
      } else if (val < 1000) {
        int div = div10(val);
        int ones = val - mul10(div); // mod 10
        val=div;
        div = div10(val);
        int tens = val - mul10(div); // mod 10
        out[wpos++] = (char)(div + '0');
        out[wpos++] = (char)(tens + '0');
        out[wpos++] = (char)(ones + '0');
      } else {
        int div = div10(val);
        int ones = val - mul10(div); // mod 10
        val=div;
        div = div10(val);
        int tens = val - mul10(div); // mod 10
        val=div;
        div = div10(val);
        int hundreds = val - mul10(div); // mod 10
  
        out[wpos++] = (char)(div + '0');
        out[wpos++] = (char)(hundreds + '0');
        out[wpos++] = (char)(tens + '0');
        out[wpos++] = (char)(ones + '0');
      }
  
  
      while (start < end) {
        val = arr[start++];
        if (neg) val = 9999 - val;
  
        int div = div10(val);
        int ones = val - mul10(div); // mod 10
        val=div;
        div = div10(val);
        int tens = val - mul10(div); // mod 10
        val=div;
        div = div10(val);
        int hundreds = val - mul10(div); // mod 10
  
        /***
        int ones = val % 10;
        val /= 10;
        int tens = val!=0 ? val % 10 : 0;
        val /= 10;
        int hundreds = val!=0 ? val % 10 : 0;
        val /= 10;
        int thousands = val!=0 ? val % 10 : 0;
        ***/
  
        /***
        int thousands = val>=1000 ? val/1000 : 0;
        int hundreds  = val>=100 ? (val/100)%10 : 0;
        int tens      = val>=10 ? (val/10)%10 : 0;
        int ones      = val % 10;
        ***/
  
        /***
        int thousands =  val/1000;
        int hundreds  = (val/100)%10;
        int tens      = (val/10)%10;
        int ones      = val % 10;
        ***/
  
        out[wpos++] = (char)(div + '0');
        out[wpos++] = (char)(hundreds + '0');
        out[wpos++] = (char)(tens + '0');
        out[wpos++] = (char)(ones + '0');
      }
  
      // OPTIONAL: if trailing zeros were truncated, then this is where
      // we would restore them (compare number of chars read vs exponent)
  
      return wpos-offset;
    }
  
  
  
  }
  