Quelle  unsigned5.hpp   Sprache: C

/*
 * Copyright (c) 1997, 2022, 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.
 *
 * 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.
 *
 */

#ifndef SHARE_UTILITIES_UNSIGNED5_HPP
#define SHARE_UTILITIES_UNSIGNED5_HPP

#include "memory/allStatic.hpp"
#include "utilities/debug.hpp"
#include "utilities/ostream.hpp"

// Low-level interface for [de-]coding compressed uint32_t (u4) values.

// A uint32_t value (32-bit unsigned int) can be encoded very quickly into
// one to five bytes, and decoded back again, again very quickly.
// This is useful for storing data, like offsets or access flags, that
// is usually simple (fits in fewer bytes usually) but sometimes has
// to be complicated (uses all five bytes when necessary).

// Notable features:
//  - represents all 32-bit uint32_t values
//  - never reads or writes beyond 5 bytes
//  - values up to 0xBE (0x307E/0xC207E/0x308207F) code in 1 byte (2/3/4 bytes)
//  - longer encodings are always of larger values (length grows monotonically)
//  - encodings are little-endian numerals in a modifed base-64 system
//  - "negatives" ((u4)-1) need 5 bytes (but see also UNSIGNED5::encode_sign)
//  - different encodings decode to different values (excepting overflow)
//  - zero bytes are *never* used, so it interoperates with null termination
//  - the algorithms are templates and cooperate well with your own types
//  - one writer algorithm can grow your resizable buffer on the fly

// The encoding, taken from J2SE Pack200, is called UNSIGNED5.
// It expects the uint32_t values you give it will have many leading zeroes.
//
// More details:
// Very small values, in the range [0..190], code in one byte.
// Any 32-bit value (including negatives) can be coded, in
// up to five bytes.  The grammar is:
//    low_byte  = [1..191]
//    high_byte = [192..255]
//    any_byte  = low_byte | high_byte
//    coding = low_byte
//           | high_byte low_byte
//           | high_byte high_byte low_byte
//           | high_byte high_byte high_byte low_byte
//           | high_byte high_byte high_byte high_byte any_byte
// Each high_byte contributes six bits of payload.
// The encoding is one-to-one (except for integer overflow)
// and easy to parse and unparse.  Longer sequences always
// decode to larger numbers.  Sequences of the same length
// compares as little-endian numerals decode to numbers which
// are ordered in the same sense as those numerals.

// Parsing (reading) consists of doing a limit test to see if the byte
// is a low-byte or a high-byte, and also unconditionally adding the
// digit value of the byte, multiplied by its 64-bit place value, to
// an accumulator.  The accumulator is returned after either 5 bytes
// are seen, or the first low-byte is seen.  Oddly enough, this is
// enough to create a dense var-int format, which is why it was
// adopted for Pack200.  By comparison, the more common LEB128 format
// is less dense (for many typical workloads) and does not guarantee a
// length limit.

class UNSIGNED5 : AllStatic {
 private:
  // Math constants for the modified UNSIGNED5 coding of Pack200
  static const int lg_H  = 6;        // log-base-2 of H (lg 64 == 6)
  static const int H     = 1<<lg_H;  // number of "high" bytes (64)
  static const int X     = 1  ;      // there is one excluded byte ('\0')
  static const int MAX_b = (1<<BitsPerByte)-1;  // largest byte value
  static const int L     = (MAX_b+1)-X-H;       // number of "low" bytes (191)

 public:
  static const int MAX_LENGTH = 5;   // lengths are in [1..5]
  static const uint32_t MAX_VALUE = (uint32_t)-1;  // 2^^32-1

  // The default method for reading and writing bytes is simply
  // b=a[i] and a[i]=b, as defined by this helpful functor.
  template<typename ARR, typename OFF>
  struct ArrayGetSet {
    uint8_t operator()(ARR a, OFF i) const { return a[i]; };
    void operator()(ARR a, OFF i, uint8_t b) const { a[i] = b; };
    // So, an expression ArrayGetSet() acts like these lambdas:
    //auto get = [&](ARR a, OFF i){ return a[i]; };
    //auto set = [&](ARR a, OFF i, uint8_t x){ a[i] = x; };
  };

  // decode a single unsigned 32-bit int from an array-like base address
  // returns the decoded value, updates offset_rw
  // that is, offset_rw is both read and written
  // warning:  caller must ensure there is at least one byte available
  // the limit is either zero meaning no limit check, or an exclusive offset
  // in PRODUCT builds, limit is ignored
  template<typename ARR, typename OFF, typename GET = ArrayGetSet<ARR,OFF>>
  static uint32_t read_uint(ARR array, OFF& offset_rw, OFF limit, GET get = GET()) {
    const OFF pos = offset_rw;
    STATIC_ASSERT(sizeof(get(array, pos)) == 1);  // must be a byte-getter
    const uint32_t b_0 = (uint8_t) get(array, pos);  //b_0 = a[0]
    assert(b_0 >= X, "avoid excluded bytes");
    uint32_t sum = b_0 - X;
    if (sum < L) {  // common case
      offset_rw = pos + 1;
      return sum;
    }
    // must collect more bytes:  b[1]...b[4]
    int lg_H_i = lg_H;  // lg(H)*i == lg(H^^i)
    for (int i = 1; ; i++) {  // for i in [1..4]
      assert(limit == 0 || pos + i < limit, "oob");
      const uint32_t b_i = (uint8_t) get(array, pos + i);  //b_i = a[i]
      assert(b_i >= X, "avoid excluded bytes");
      sum += (b_i - X) << lg_H_i;  // sum += (b[i]-X)*(64^^i)
      if (b_i < X+L || i == MAX_LENGTH-1) {
        offset_rw = pos + i + 1;
        return sum;
      }
      lg_H_i += lg_H;
    }
  }

  // encode a single unsigned 32-bit int into an array-like span
  // offset_rw is both read and written
  // the limit is either zero meaning no limit check, or an exclusive offset
  // warning:  caller must ensure there is available space
  template<typename ARR, typename OFF, typename SET = ArrayGetSet<ARR,OFF>>
  static void write_uint(uint32_t value, ARR array, OFF& offset_rw, OFF limit, SET set = SET()) {
    const OFF pos = offset_rw;
    if (value < L) {
      const uint32_t b_0 = X + value;
      assert(b_0 == (uint8_t)b_0, "valid byte");
      set(array, pos, (uint8_t)b_0);  //a[0] = b_0
      offset_rw = pos + 1;
      return;
    }
    uint32_t sum = value;
    for (int i = 0; ; i++) {  // for i in [0..4]
      if (sum < L || i == MAX_LENGTH-1) {
        // remainder is either a "low code" or the 5th byte
        uint32_t b_i = X + sum;
        assert(b_i == (uint8_t)b_i, "valid byte");
        set(array, pos + i, (uint8_t)b_i);  //a[i] = b_i
        offset_rw = pos + i + 1;
        return;
      }
      sum -= L;
      uint32_t b_i = X + L + (sum % H);  // this is a "high code"
      assert(b_i == (uint8_t)b_i, "valid byte");
      set(array, pos + i, (uint8_t)b_i);  //a[i] = b_i
      sum >>= lg_H;                 // extracted 6 bits
    }
  }

  // returns the encoded byte length of an unsigned 32-bit int
  static constexpr int encoded_length(uint32_t value) {
    // model the reading of [0..5] high-bytes, followed possibly by a low-byte
    // Be careful:  the constexpr magic evaporates if undefined behavior
    // results from any of these expressions.  Beware of signed overflow!
    uint32_t sum = 0;
    uint32_t lg_H_i = 0;
    for (uint32_t i = 0; ; i++) {  // for i in [1..4]
      if (value <= sum + ((L-1) << lg_H_i) || i == MAX_LENGTH-1) {
        return i + 1;  // stopping at byte i implies length is i+1
      }
      sum += (MAX_b - X) << lg_H_i;
      lg_H_i += lg_H;
    }
  }

  // reports the largest uint32_t value that can be encoded using len bytes
  // len must be in the range [1..5]
  static constexpr uint32_t max_encoded_in_length(uint32_t len) {
    assert(len >= 1 && len <= MAX_LENGTH, "invalid length");
    if (len >= MAX_LENGTH)  return MAX_VALUE;  // largest non-overflow value
    // Be careful:  the constexpr magic evaporates if undefined behavior
    // results from any of these expressions.  Beware of signed overflow!
    uint32_t all_combinations = 0;
    uint32_t combinations_i = L;  // L * H^i
    for (uint32_t i = 0; i < len; i++) {
      // count combinations of <H*L> that end at byte i
      all_combinations += combinations_i;
      combinations_i <<= lg_H;
    }
    return all_combinations - 1;
  }

  // tells if a value, when encoded, would fit between the offset and limit
  template<typename OFF>
  static constexpr bool fits_in_limit(uint32_t value, OFF offset, OFF limit) {
    assert(limit != 0, "");
    return (offset + MAX_LENGTH <= limit ||
            offset + encoded_length(value) <= limit);
  }

  // parses one encoded value for correctness and returns the size,
  // or else returns zero if there is a problem (bad limit or excluded byte)
  // the limit is either zero meaning no limit check, or an exclusive offset
  template<typename ARR, typename OFF, typename GET = ArrayGetSet<ARR,OFF>>
  static int check_length(ARR array, OFF offset, OFF limit = 0,
                          GET get = GET()) {
    const OFF pos = offset;
    STATIC_ASSERT(sizeof(get(array, pos)) == 1);  // must be a byte-getter
    const uint32_t b_0 = (uint8_t) get(array, pos);  //b_0 = a[0]
    if (b_0 < X+L) {
      return (b_0 < X) ? 0 : 1;
    }
    // parse more bytes:  b[1]...b[4]
    for (int i = 1; ; i++) {  // for i in [1..4]
      if (limit != 0 && pos + i >= limit)  return 0;  // limit failure
      const uint32_t b_i = (uint8_t) get(array, pos + i);  //b_i = a[i]
      if (b_i < X)  return 0;  // excluded byte found
      if (b_i < X+L || i == MAX_LENGTH-1) {
        return i + 1;
      }
    }
  }

  template<typename ARR, typename OFF, typename GFN,
           typename SET = ArrayGetSet<ARR,OFF>>
  static void write_uint_grow(uint32_t value,
                              ARR& array, OFF& offset, OFF& limit,
                              GFN grow, SET set = SET()) {
    assert(limit != 0, "limit required");
    const OFF pos = offset;
    if (!fits_in_limit(value, pos, limit)) {
      grow(MAX_LENGTH);  // caller must ensure it somehow fixes array/limit span
      assert(pos + MAX_LENGTH <= limit, "should have grown");
    }
    write_uint(value, array, offset, limit, set);
  }

  /// Handy state machines for that will help you with reading,
  /// sizing, and writing (with optional growth).

  // Reader example use:
  //  struct MyReaderHelper {
  //    char operator()(char* a, int i) const { return a[i]; }
  //  };
  //  using MyReader = UNSIGNED5::Reader<char*, int, MyReaderHelper>;
  //  MyReader r(array); while (r.has_next())  print(r.next_uint());
  template<typename ARR, typename OFF, typename GET = ArrayGetSet<ARR,OFF>>
  class Reader {
    const ARR _array;
    const OFF _limit;
    OFF _position;
    int next_length() {
      return UNSIGNED5::check_length(_array, _position, _limit, GET());
    }
  public:
    Reader(ARR array, OFF limit = 0)
      : _array(array), _limit(limit) { _position = 0; }
    uint32_t next_uint() {
      return UNSIGNED5::read_uint(_array, _position, _limit, GET());
    }
    bool has_next() {
      return next_length() != 0;
    }
    // tries to skip count logical entries; returns actual number skipped
    int try_skip(int count) {
      int actual = 0;
      while (actual < count && has_next()) {
        int len = next_length();  // 0 or length in [1..5]
        if (len == 0)  break;
        _position += len;
      }
      return actual;
    }
    ARR array() { return _array; }
    OFF limit() { return _limit; }
    OFF position() { return _position; }
    void set_position(OFF position) { _position = position; }

    // For debugging, even in product builds (see debug.cpp).
    // Checks and decodes a series of u5 values from the reader.
    // Sets position just after the last decoded byte or null byte.
    // If this reader has a limit, stop before that limit.
    // If this reader has no limit, stop after the first null byte.
    // In any case, if count is non-negative, print no more than
    // count items (uint32_t values or "null").
    // A negative count means we stop only at the limit or null,
    // kind of like strlen.
    void print(int count = -1) { print_on(tty, count); }

    // The character strings are printed before and after the
    // series of values (which are separated only by spaces).
    // If they are null they default to something like "U5:[ "
    // and " ] (values=%d/length=%d)\n".
    // The %d formats are for the number of printed items and
    // their length in bytes, if you want to see that also.
    void print_on(outputStream* st, int count = -1,
                  const char* left = NULL, const char* right = NULL);
  };

  // Writer example use
  //  struct MyWriterHelper {
  //    char operator()(char* a, int i, char b) const { a[i] = b; }
  //  };
  //  using MyWriter = UNSIGNED5::Writer<char*, int, MyWriterHelper>;
  //  MyWriter w(array);
  //  for (auto i = ...)  w.accept_uint(i);
  template<typename ARR, typename OFF, typename SET = ArrayGetSet<ARR,OFF>>
  class Writer {
    ARR& _array;
    OFF* const _limit_ptr;
    OFF _position;
  public:
    Writer(const ARR& array)
      : _array(const_cast<ARR&>(array)), _limit_ptr(NULL), _position(0) {
      // Note: if _limit_ptr is NULL, the ARR& is never reassigned,
      // because has_limit is false.  So the const_cast here is safe.
      assert(!has_limit(), "this writer cannot be growable");
    }
    Writer(ARR& array, OFF& limit)
      : _array(array), _limit_ptr(&limit), _position(0) {
      // Writable array argument can be rewritten by accept_grow.
      // So we need a legitimate (non-zero) limit to work with.
      // As a result, a writer's initial buffer must not be empty.
      assert(this->limit() != 0, "limit required");
    }
    void accept_uint(uint32_t value) {
      const OFF lim = has_limit() ? limit() : 0;
      UNSIGNED5::write_uint(value, _array, _position, lim, SET());
    }
    template<typename GFN>
    void accept_grow(uint32_t value, GFN grow) {
      assert(has_limit(), "must track growing limit");
      UNSIGNED5::write_uint_grow(value, _array, _position, *_limit_ptr,
                                 grow, SET());
    }
    // Ensure that remaining() >= r, grow if needed.  Suggested
    // expression for r is (n*MAX_LENGTH)+1, where n is the number of
    // values you are about to write.
    template<typename GFN>
    void ensure_remaining_grow(int request_remaining, GFN grow) {
      const OFF have = remaining();
      if (have < request_remaining) {
        grow(have - request_remaining);  // caller must fix array/limit span
        assert(remaining() >= request_remaining, "should have grown");
      }
    }
    // use to add a terminating null or other data
    void end_byte(uint8_t extra_byte = 0) {
      SET()(_array, _position++, extra_byte);
    }
    ARR array() { return _array; }
    OFF position() { return _position; }
    void set_position(OFF position) { _position = position; }
    bool has_limit() { return _limit_ptr != NULL; }
    OFF limit() { assert(has_limit(), "needs limit"); return *_limit_ptr; }
    OFF remaining() { return limit() - position(); }
  };

  // Sizer example use
  //  UNSIGNED5::Sizer s;
  //  for (auto i = ...)  s.accept_uint(i);
  //  printf("%d items occupying %d bytes", s.count(), s.position());
  //  auto buf = new char[s.position() + 1];
  //  UNSIGNED5::Writer<char*, int> w(buf);
  //  for (auto i = ...)  w.accept_uint(i);
  //  w.add_byte();
  //  assert(w.position() == s.position(), "s and w agree");
  template<typename OFF = int>
  class Sizer {
    OFF _position;
    int _count;
  public:
    Sizer() { _position = 0; _count = 0; }
    // The accept_uint() API is the same as for Writer, which allows
    // templated code to work equally well on sizers and writers.
    // This in turn makes it easier to write code which runs a
    // sizing preflight pass before actually storing the data.
    void accept_uint(uint32_t value) {
      _position += encoded_length(value);
      _count++;
    }
    OFF position() { return _position; }
    int count() { return _count; }
  };

  // 32-bit one-to-one sign encoding taken from Pack200
  // converts leading sign bits into leading zeroes with trailing sign bit
  // use this to better compress 32-bit values that might be negative
  static uint32_t encode_sign(int32_t value) { return ((uint32_t)value << 1) ^ (value >> 31); }
  static int32_t decode_sign(uint32_t value) { return (value >> 1) ^ -(int32_t)(value & 1); }

  template<typename ARR, typename OFF, typename GET = ArrayGetSet<ARR,OFF>>
  static OFF print(ARR array, OFF offset = 0, OFF limit = 0,
                   GET get = GET()) {
    print_count(-1, array, offset, limit, get);
  }
  template<typename ARR, typename OFF, typename GET = ArrayGetSet<ARR,OFF>>
  static OFF print_count(int count,
                         ARR array, OFF offset = 0, OFF limit = 0,
                         GET get = GET()) {
    Reader<ARR,OFF,GET> r(array, offset);

    r.print_on(tty, count);
    return r.position();
  }
};
#endif // SHARE_UTILITIES_UNSIGNED5_HPP