1 /*

     2  * Copyright (c) 2002, 2008, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 struct unpacker;

    27 

    28 #define INT_MAX_VALUE ((int)0x7FFFFFFF)

    29 #define INT_MIN_VALUE ((int)0x80000000)

    30 

    31 #define CODING_SPEC(B, H, S, D) ((B)<<20|(H)<<8|(S)<<4|(D)<<0)

    32 #define CODING_B(x) ((x)>>20 & 0xF)

    33 #define CODING_H(x) ((x)>>8  & 0xFFF)

    34 #define CODING_S(x) ((x)>>4  & 0xF)

    35 #define CODING_D(x) ((x)>>0  & 0xF)

    36 

    37 #define CODING_INIT(B, H, S, D) \

    38   { CODING_SPEC(B, H, S, D) , 0, 0, 0, 0, 0, 0, 0, 0}

    39 

    40 // For debugging purposes, some compilers do not like this and will complain.

    41 //    #define long do_not_use_C_long_types_use_jlong_or_int

    42 // Use of the type "long" is problematic, do not use it.

    43 

    44 struct coding {

    45   int  spec;  // B,H,S,D

    46 

    47   // Handy values derived from the spec:

    48   int B() { return CODING_B(spec); }

    49   int H() { return CODING_H(spec); }

    50   int S() { return CODING_S(spec); }

    51   int D() { return CODING_D(spec); }

    52   int L() { return 256-CODING_H(spec); }

    53   int  min, max;

    54   int  umin, umax;

    55   char isSigned, isSubrange, isFullRange, isMalloc;

    56 

    57   coding* init();  // returns self or null if error

    58   coding* initFrom(int spec_) {

    59     assert(this->spec == 0);

    60     this->spec = spec_;

    61     return init();

    62   }

    63 

    64   static coding* findBySpec(int spec);

    65   static coding* findBySpec(int B, int H, int S=0, int D=0);

    66   static coding* findByIndex(int irregularCodingIndex);

    67 

    68   static uint parse(byte* &rp, int B, int H);

    69   static uint parse_lgH(byte* &rp, int B, int H, int lgH);

    70   static void parseMultiple(byte* &rp, int N, byte* limit, int B, int H);

    71 

    72   uint parse(byte* &rp) {

    73     return parse(rp, CODING_B(spec), CODING_H(spec));

    74   }

    75   void parseMultiple(byte* &rp, int N, byte* limit) {

    76     parseMultiple(rp, N, limit, CODING_B(spec), CODING_H(spec));

    77   }

    78 

    79   bool canRepresent(int x)         { return (x >= min  && x <= max);  }

    80   bool canRepresentUnsigned(int x) { return (x >= umin && x <= umax); }

    81 

    82   int sumInUnsignedRange(int x, int y);

    83 

    84   int readFrom(byte* &rpVar, int* dbase);

    85   void readArrayFrom(byte* &rpVar, int* dbase, int length, int* values);

    86   void skipArrayFrom(byte* &rpVar, int length) {

    87     readArrayFrom(rpVar, (int*)NULL, length, (int*)NULL);

    88   }

    89 

    90 #ifndef PRODUCT

    91   const char* string();

    92 #endif

    93 

    94   void free();  // free self if isMalloc

    95 

    96   // error handling

    97   static void abort(const char* msg = null) { unpack_abort(msg); }

    98 };

    99 

   100 enum coding_method_kind {

   101   cmk_ERROR,

   102   cmk_BHS,

   103   cmk_BHS0,

   104   cmk_BHS1,

   105   cmk_BHSD1,

   106   cmk_BHS1D1full,  // isFullRange

   107   cmk_BHS1D1sub,   // isSubRange

   108 

   109   // special cases hand-optimized (~50% of all decoded values)

   110   cmk_BYTE1,         //(1,256)      6%

   111   cmk_CHAR3,         //(3,128)      7%

   112   cmk_UNSIGNED5,     //(5,64)      13%

   113   cmk_DELTA5,        //(5,64,1,1)   5%

   114   cmk_BCI5,          //(5,4)       18%

   115   cmk_BRANCH5,       //(5,4,2)      4%

   116 //cmk_UNSIGNED5H16,  //(5,16)       5%

   117 //cmk_UNSIGNED2H4,   //(2,4)        6%

   118 //cmk_DELTA4H8,      //(4,8,1,1)   10%

   119 //cmk_DELTA3H16,     //(3,16,1,1)   9%

   120   cmk_BHS_LIMIT,

   121 

   122   cmk_pop,

   123   cmk_pop_BHS0,

   124   cmk_pop_BYTE1,

   125   cmk_pop_LIMIT,

   126 

   127   cmk_LIMIT

   128 };

   129 

   130 enum {

   131   BYTE1_spec       = CODING_SPEC(1, 256, 0, 0),

   132   CHAR3_spec       = CODING_SPEC(3, 128, 0, 0),

   133   UNSIGNED4_spec   = CODING_SPEC(4, 256, 0, 0),

   134   UNSIGNED5_spec   = CODING_SPEC(5, 64, 0, 0),

   135   SIGNED5_spec     = CODING_SPEC(5, 64, 1, 0),

   136   DELTA5_spec      = CODING_SPEC(5, 64, 1, 1),

   137   UDELTA5_spec     = CODING_SPEC(5, 64, 0, 1),

   138   MDELTA5_spec     = CODING_SPEC(5, 64, 2, 1),

   139   BCI5_spec        = CODING_SPEC(5, 4, 0, 0),

   140   BRANCH5_spec     = CODING_SPEC(5, 4, 2, 0)

   141 };

   142 

   143 enum {

   144   B_MAX = 5,

   145   C_SLOP = B_MAX*10

   146 };

   147 

   148 struct coding_method;

   149 

   150 // iterator under the control of a meta-coding

   151 struct value_stream {

   152   // current coding of values or values

   153   coding c;               // B,H,S,D,etc.

   154   coding_method_kind cmk; // type of decoding needed

   155   byte* rp;               // read pointer

   156   byte* rplimit;          // final value of read pointer

   157   int sum;                // partial sum of all values so far (D=1 only)

   158   coding_method* cm;      // coding method that defines this stream

   159 

   160   void init(byte* band_rp, byte* band_limit, coding* defc);

   161   void init(byte* band_rp, byte* band_limit, int spec)

   162     { init(band_rp, band_limit, coding::findBySpec(spec)); }

   163 

   164   void setCoding(coding* c);

   165   void setCoding(int spec) { setCoding(coding::findBySpec(spec)); }

   166 

   167   // Parse and decode a single value.

   168   int getInt();

   169 

   170   // Parse and decode a single byte, with no error checks.

   171   int getByte() {

   172     assert(cmk == cmk_BYTE1);

   173     assert(rp < rplimit);

   174     return *rp++ & 0xFF;

   175   }

   176 

   177   // Used only for asserts.

   178   bool hasValue();

   179 

   180   void done() { assert(!hasValue()); }

   181 

   182   // Sometimes a value stream has an auxiliary (but there are never two).

   183   value_stream* helper() {

   184     assert(hasHelper());

   185     return this+1;

   186   }

   187   bool hasHelper();

   188 

   189   // error handling

   190   //  inline void abort(const char* msg);

   191   //  inline void aborting();

   192 };

   193 

   194 struct coding_method {

   195   value_stream vs0;       // initial state snapshot (vs.meta==this)

   196 

   197   coding_method* next;    // what to do when we run out of bytes

   198 

   199   // these fields are used for pop codes only:

   200   int* fValues;           // favored value array

   201   int  fVlength;          // maximum favored value token

   202   coding_method* uValues; // unfavored value stream

   203 

   204   // pointer to outer unpacker, for error checks etc.

   205   unpacker* u;

   206 

   207   // Initialize a value stream.

   208   void reset(value_stream* state);

   209 

   210   // Parse a band header, size a band, and initialize for further action.

   211   // band_rp advances (but not past band_limit), and meta_rp advances.

   212   // The mode gives context, such as "inside a pop".

   213   // The defc and N are the incoming parameters to a meta-coding.

   214   // The value sink is used to collect output values, when desired.

   215   void init(byte* &band_rp, byte* band_limit,

   216             byte* &meta_rp, int mode,

   217             coding* defc, int N,

   218             intlist* valueSink);

   219 

   220   // error handling

   221   void abort(const char* msg) { unpack_abort(msg, u); }

   222   bool aborting()             { return unpack_aborting(u); }

   223 };

   224 

   225 //inline void value_stream::abort(const char* msg) { cm->abort(msg); }

   226 //inline void value_stream::aborting()             { cm->aborting(); }