/*

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

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

 *

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

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

 * published by the Free Software Foundation.  Oracle designates this

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

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

 *

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

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

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

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

 * accompanied this code).

 *

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

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

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

 *

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

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

 * questions.

 */

// -*- C++ -*-

// Small program for unpacking specially compressed Java packages.

// John R. Rose

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdarg.h>

#include "defines.h"

#include "bytes.h"

#include "utils.h"

#include "coding.h"

#include "constants.h"

#include "unpack.h"

extern coding basic_codings[];

#define CODING_PRIVATE(spec) \

  int spec_ = spec; \

  int B = CODING_B(spec_); \

  int H = CODING_H(spec_); \

  int L = 256 - H; \

  int S = CODING_S(spec_); \

  int D = CODING_D(spec_)

#define IS_NEG_CODE(S, codeVal) \

  ( (((int)(codeVal)+1) & ((1<<S)-1)) == 0 )

#define DECODE_SIGN_S1(ux) \

  ( ((uint)(ux) >> 1) ^ -((int)(ux) & 1) )

static maybe_inline

int decode_sign(int S, uint ux) {  // == Coding.decodeSign32

  assert(S > 0);

  uint sigbits = (ux >> S);

  if (IS_NEG_CODE(S, ux))

    return (int)(    ~sigbits);

  else

    return (int)(ux - sigbits);

  // Note that (int)(ux-sigbits) can be negative, if ux is large enough.

}

coding* coding::init() {

  if (umax > 0)  return this;  // already done

  assert(spec != 0);  // sanity

  // fill in derived fields

  CODING_PRIVATE(spec);

  // Return null if 'arb(BHSD)' parameter constraints are not met:

  if (B < 1 || B > B_MAX)  return null;

  if (H < 1 || H > 256)    return null;

  if (S < 0 || S > 2)      return null;

  if (D < 0 || D > 1)      return null;

  if (B == 1 && H != 256)  return null;  // 1-byte coding must be fixed-size

  if (B >= 5 && H == 256)  return null;  // no 5-byte fixed-size coding

  // first compute the range of the coding, in 64 bits

  jlong range = 0;

  {

    jlong H_i = 1;

    for (int i = 0; i < B; i++) {

      range += H_i;

      H_i *= H;

    }

    range *= L;

    range += H_i;

  }

  assert(range > 0);  // no useless codings, please

  int this_umax;

  // now, compute min and max

  if (range >= ((jlong)1 << 32)) {

    this_umax  = INT_MAX_VALUE;

    this->umin = INT_MIN_VALUE;

    this->max  = INT_MAX_VALUE;

    this->min  = INT_MIN_VALUE;

  } else {

    this_umax = (range > INT_MAX_VALUE) ? INT_MAX_VALUE : (int)range-1;

    this->max = this_umax;

    this->min = this->umin = 0;

    if (S != 0 && range != 0) {

      int Smask = (1<<S)-1;

      jlong maxPosCode = range-1;

      jlong maxNegCode = range-1;

      while (IS_NEG_CODE(S,  maxPosCode))  --maxPosCode;

      while (!IS_NEG_CODE(S, maxNegCode))  --maxNegCode;

      int maxPos = decode_sign(S, (uint)maxPosCode);

      if (maxPos < 0)

        this->max = INT_MAX_VALUE;  // 32-bit wraparound

      else

        this->max = maxPos;

      if (maxNegCode < 0)

        this->min = 0;  // No negative codings at all.

      else

        this->min = decode_sign(S, (uint)maxNegCode);

    }

  }

  assert(!(isFullRange | isSigned | isSubrange)); // init

  if (min < 0)

    this->isSigned = true;

  if (max < INT_MAX_VALUE && range <= INT_MAX_VALUE)

    this->isSubrange = true;

  if (max == INT_MAX_VALUE && min == INT_MIN_VALUE)

    this->isFullRange = true;

  // do this last, to reduce MT exposure (should have a membar too)

  this->umax = this_umax;

  return this;

}

coding* coding::findBySpec(int spec) {

  for (coding* scan = &basic_codings[0]; ; scan++) {

    if (scan->spec == spec)

      return scan->init();

    if (scan->spec == 0)

      break;

  }

  coding* ptr = NEW(coding, 1);

  CHECK_NULL_0(ptr);

  coding* c = ptr->initFrom(spec);

  if (c == null) {

    mtrace('f', ptr, 0);

    ::free(ptr);

  } else

    // else caller should free it...

    c->isMalloc = true;

  return c;

}

coding* coding::findBySpec(int B, int H, int S, int D) {

  if (B < 1 || B > B_MAX)  return null;

  if (H < 1 || H > 256)    return null;

  if (S < 0 || S > 2)      return null;

  if (D < 0 || D > 1)      return null;

  return findBySpec(CODING_SPEC(B, H, S, D));

}

void coding::free() {

  if (isMalloc) {

    mtrace('f', this, 0);

    ::free(this);

  }

}

void coding_method::reset(value_stream* state) {

  assert(state->rp == state->rplimit);  // not in mid-stream, please

  //assert(this == vs0.cm);

  state[0] = vs0;

  if (uValues != null) {

    uValues->reset(state->helper());

  }

}

maybe_inline

uint coding::parse(byte* &rp, int B, int H) {

  int L = 256-H;

  byte* ptr = rp;

  // hand peel the i==0 part of the loop:

  uint b_i = *ptr++ & 0xFF;

  if (B == 1 || b_i < (uint)L)

    { rp = ptr; return b_i; }

  uint sum = b_i;

  uint H_i = H;

  assert(B <= B_MAX);

  for (int i = 2; i <= B_MAX; i++) { // easy for compilers to unroll if desired

    b_i = *ptr++ & 0xFF;

    sum += b_i * H_i;

    if (i == B || b_i < (uint)L)

      { rp = ptr; return sum; }

    H_i *= H;

  }

  assert(false);

  return 0;

}

maybe_inline

uint coding::parse_lgH(byte* &rp, int B, int H, int lgH) {

  assert(H == (1<<lgH));

  int L = 256-(1<<lgH);

  byte* ptr = rp;

  // hand peel the i==0 part of the loop:

  uint b_i = *ptr++ & 0xFF;

  if (B == 1 || b_i < (uint)L)

    { rp = ptr; return b_i; }

  uint sum = b_i;

  uint lg_H_i = lgH;

  assert(B <= B_MAX);

  for (int i = 2; i <= B_MAX; i++) { // easy for compilers to unroll if desired

    b_i = *ptr++ & 0xFF;

    sum += b_i << lg_H_i;

    if (i == B || b_i < (uint)L)

      { rp = ptr; return sum; }

    lg_H_i += lgH;

  }

  assert(false);

  return 0;

}

static const char ERB[] = "EOF reading band";

maybe_inline

void coding::parseMultiple(byte* &rp, int N, byte* limit, int B, int H) {

  if (N < 0) {

    abort("bad value count");

    return;

  }

  byte* ptr = rp;

  if (B == 1 || H == 256) {

    size_t len = (size_t)N*B;

    if (len / B != (size_t)N || ptr+len > limit) {

      abort(ERB);

      return;

    }

    rp = ptr+len;

    return;

  }

  // Note:  We assume rp has enough zero-padding.

  int L = 256-H;

  int n = B;

  while (N > 0) {

    ptr += 1;

    if (--n == 0) {

      // end of encoding at B bytes, regardless of byte value

    } else {

      int b = (ptr[-1] & 0xFF);

      if (b >= L) {

        // keep going, unless we find a byte < L

        continue;

      }

    }

    // found the last byte

    N -= 1;

    n = B;   // reset length counter

    // do an error check here

    if (ptr > limit) {

      abort(ERB);

      return;

    }

  }

  rp = ptr;

  return;

}

bool value_stream::hasHelper() {

  // If my coding method is a pop-style method,

  // then I need a second value stream to transmit

  // unfavored values.

  // This can be determined by examining fValues.

  return cm->fValues != null;

}

void value_stream::init(byte* rp_, byte* rplimit_, coding* defc) {

  rp = rp_;

  rplimit = rplimit_;

  sum = 0;

  cm = null;  // no need in the simple case

  setCoding(defc);

}

void value_stream::setCoding(coding* defc) {

  if (defc == null) {

    unpack_abort("bad coding");

    defc = coding::findByIndex(_meta_canon_min);  // random pick for recovery

  }

  c = (*defc);

  // choose cmk

  cmk = cmk_ERROR;

  switch (c.spec) {

  case BYTE1_spec:      cmk = cmk_BYTE1;        break;

  case CHAR3_spec:      cmk = cmk_CHAR3;        break;

  case UNSIGNED5_spec:  cmk = cmk_UNSIGNED5;    break;

  case DELTA5_spec:     cmk = cmk_DELTA5;       break;

  case BCI5_spec:       cmk = cmk_BCI5;         break;

  case BRANCH5_spec:    cmk = cmk_BRANCH5;      break;

  default:

    if (c.D() == 0) {

      switch (c.S()) {

      case 0:  cmk = cmk_BHS0;  break;

      case 1:  cmk = cmk_BHS1;  break;

      default: cmk = cmk_BHS;   break;

      }

    } else {

      if (c.S() == 1) {

        if (c.isFullRange)   cmk = cmk_BHS1D1full;

        if (c.isSubrange)    cmk = cmk_BHS1D1sub;

      }

      if (cmk == cmk_ERROR)  cmk = cmk_BHSD1;

    }

  }

}

static maybe_inline

int getPopValue(value_stream* self, uint uval) {

  if (uval > 0) {

    // note that the initial parse performed a range check

    assert(uval <= (uint)self->cm->fVlength);

    return self->cm->fValues[uval-1];

  } else {

    // take an unfavored value

    return self->helper()->getInt();

  }

}

maybe_inline

int coding::sumInUnsignedRange(int x, int y) {

  assert(isSubrange);

  int range = (int)(umax+1);

  assert(range > 0);

  x += y;

  if (x != (int)((jlong)(x-y) + (jlong)y)) {

    // 32-bit overflow interferes with range reduction.

    // Back off from the overflow by adding a multiple of range:

    if (x < 0) {

      x -= range;

      assert(x >= 0);

    } else {

      x += range;

      assert(x < 0);

    }

  }

  if (x < 0) {

    x += range;

    if (x >= 0)  return x;

  } else if (x >= range) {

    x -= range;

    if (x < range)  return x;

  } else {

    // in range

    return x;

  }

  // do it the hard way

  x %= range;

  if (x < 0)  x += range;

  return x;

}

static maybe_inline

int getDeltaValue(value_stream* self, uint uval, bool isSubrange) {

  assert((uint)(self->c.isSubrange) == (uint)isSubrange);

  assert(self->c.isSubrange | self->c.isFullRange);

  if (isSubrange)

    return self->sum = self->c.sumInUnsignedRange(self->sum, (int)uval);

  else

    return self->sum += (int) uval;

}

bool value_stream::hasValue() {

  if (rp < rplimit)      return true;

  if (cm == null)        return false;

  if (cm->next == null)  return false;

  cm->next->reset(this);

  return hasValue();

}

int value_stream::getInt() {

  if (rp >= rplimit) {

    // Advance to next coding segment.

    if (rp > rplimit || cm == null || cm->next == null) {

      // Must perform this check and throw an exception on bad input.

      unpack_abort(ERB);

      return 0;

    }

    cm->next->reset(this);

    return getInt();

  }

  CODING_PRIVATE(c.spec);

  uint uval;

  enum {

    B5 = 5,

    B3 = 3,

    H128 = 128,

    H64 = 64,

    H4 = 4

  };

  switch (cmk) {

  case cmk_BHS:

    assert(D == 0);

    uval = coding::parse(rp, B, H);

    if (S == 0)

      return (int) uval;

    return decode_sign(S, uval);

  case cmk_BHS0:

    assert(S == 0 && D == 0);

    uval = coding::parse(rp, B, H);

    return (int) uval;

  case cmk_BHS1:

    assert(S == 1 && D == 0);

    uval = coding::parse(rp, B, H);

    return DECODE_SIGN_S1(uval);

  case cmk_BYTE1:

    assert(c.spec == BYTE1_spec);

    assert(B == 1 && H == 256 && S == 0 && D == 0);

    return *rp++ & 0xFF;

  case cmk_CHAR3:

    assert(c.spec == CHAR3_spec);

    assert(B == B3 && H == H128 && S == 0 && D == 0);

    return coding::parse_lgH(rp, B3, H128, 7);

  case cmk_UNSIGNED5:

    assert(c.spec == UNSIGNED5_spec);

    assert(B == B5 && H == H64 && S == 0 && D == 0);

    return coding::parse_lgH(rp, B5, H64, 6);

  case cmk_BHSD1:

    assert(D == 1);

    uval = coding::parse(rp, B, H);

    if (S != 0)

      uval = (uint) decode_sign(S, uval);

    return getDeltaValue(this, uval, (bool)c.isSubrange);

  case cmk_BHS1D1full:

    assert(S == 1 && D == 1 && c.isFullRange);

    uval = coding::parse(rp, B, H);

    uval = (uint) DECODE_SIGN_S1(uval);

    return getDeltaValue(this, uval, false);

  case cmk_BHS1D1sub:

    assert(S == 1 && D == 1 && c.isSubrange);

    uval = coding::parse(rp, B, H);

    uval = (uint) DECODE_SIGN_S1(uval);

    return getDeltaValue(this, uval, true);

  case cmk_DELTA5:

    assert(c.spec == DELTA5_spec);

    assert(B == B5 && H == H64 && S == 1 && D == 1 && c.isFullRange);

    uval = coding::parse_lgH(rp, B5, H64, 6);

    sum += DECODE_SIGN_S1(uval);

    return sum;

  case cmk_BCI5:

    assert(c.spec == BCI5_spec);

    assert(B == B5 && H == H4 && S == 0 && D == 0);

    return coding::parse_lgH(rp, B5, H4, 2);

  case cmk_BRANCH5:

    assert(c.spec == BRANCH5_spec);

    assert(B == B5 && H == H4 && S == 2 && D == 0);

    uval = coding::parse_lgH(rp, B5, H4, 2);

    return decode_sign(S, uval);

  case cmk_pop:

    uval = coding::parse(rp, B, H);

    if (S != 0) {

      uval = (uint) decode_sign(S, uval);

    }

    if (D != 0) {

      assert(c.isSubrange | c.isFullRange);

      if (c.isSubrange)

        sum = c.sumInUnsignedRange(sum, (int) uval);

      else

        sum += (int) uval;

      uval = (uint) sum;

    }

    return getPopValue(this, uval);

  case cmk_pop_BHS0:

    assert(S == 0 && D == 0);

    uval = coding::parse(rp, B, H);

    return getPopValue(this, uval);

  case cmk_pop_BYTE1:

    assert(c.spec == BYTE1_spec);

    assert(B == 1 && H == 256 && S == 0 && D == 0);

    return getPopValue(this, *rp++ & 0xFF);

  default:

    break;

  }

  assert(false);

  return 0;

}

static maybe_inline

int moreCentral(int x, int y) {  // used to find end of Pop.{F}

  // Suggested implementation from the Pack200 specification:

  uint kx = (x >> 31) ^ (x << 1);

  uint ky = (y >> 31) ^ (y << 1);

  return (kx < ky? x: y);

}

//static maybe_inline

//int moreCentral2(int x, int y, int min) {

//  // Strict implementation of buggy 150.7 specification.

//  // The bug is that the spec. says absolute-value ties are broken

//  // in favor of positive numbers, but the suggested implementation

//  // (also mentioned in the spec.) breaks ties in favor of negative numbers.

//  if ((x + y) != 0)