#306

Committed 30 Apr 2024 10:01PM UTC coverage: 97.645% (-0.5%) from 98.139%

Build # #306

Build Type

push

Committed by

Commit Message

Merge pull request #555 from apache/fix_pom_xml_header

Fix pom xml header

Run Details

26865 of 27513 relevant lines covered (97.64%)

0.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.97

/src/main/java/org/apache/datasketches/hll/PreambleUtil.java

/*
 * 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.datasketches.hll;

import static org.apache.datasketches.common.Util.LS;
import static org.apache.datasketches.common.Util.ceilingPowerOf2;
import static org.apache.datasketches.common.Util.exactLog2OfLong;
import static org.apache.datasketches.common.Util.zeroPad;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
import static org.apache.datasketches.hll.HllUtil.LG_INIT_SET_SIZE;
import static org.apache.datasketches.hll.HllUtil.RESIZE_DENOM;
import static org.apache.datasketches.hll.HllUtil.RESIZE_NUMER;

import java.nio.ByteOrder;

import org.apache.datasketches.common.Family;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;

//@formatter:off
/**
 * <pre>
 * CouponList Layout
 * Long || Start Byte Adr, Big Endian Illustration
 * Adr:
 *      ||    7   |    6   |    5   |    4   |    3   |    2   |    1   |    0   |
 *  0   ||  Mode  | ListCnt| Flags  |  LgArr |   lgK  | FamID  | SerVer |  PI=2  |
 *
 *      ||   15   |   14   |   13   |   12   |   11   |   10   |    9   |    8   |
 *  1   ||                                   |------Coupon Int List Start--------|
 * </pre>
 *
 *  <pre>
 * CouponHashSet Layout
 * Long || Start Byte Adr, Big Endian Illustration
 * Adr:
 *      ||    7   |    6   |    5   |    4   |    3   |    2   |    1   |    0   |
 *  0   ||  Mode  |        | Flags  |  LgArr |   lgK  | FamID  | SerVer |  PI=3  |
 *
 *      ||   15   |   14   |   13   |   12   |   11   |   10   |    9   |    8   |
 *  1   ||-----Coupon Int Hash Set Start-----|---------Hash Set Count------------|
 * </pre>
 *
 * <pre>
 * HllArray Layout
 * Long || Start Byte Adr, Big Endian Illustration
 * Adr:
 *      ||    7   |    6   |    5   |    4   |    3   |    2   |    1   |    0   |
 *  0   ||  Mode  | CurMin | Flags  |  LgArr |   lgK  | FamID  | SerVer | PI=10  |
 *
 *      ||   15   |   14   |   13   |   12   |   11   |   10   |    9   |    8   |
 *  1   ||-------------------------------HIP Accum-------------------------------|
 *
 *      ||   23   |   22   |   21   |   20   |   19   |   18   |   17   |   16   |
 *  2   ||----------------------------------KxQ0---------------------------------|
 *
 *      ||   31   |   30   |   29   |   28   |   27   |   26   |   25   |   24   |
 *  3   ||----------------------------------KxQ1---------------------------------|
 *
 *      ||   39   |   38   |   37   |   36   |   35   |   34   |   33   |   32   |
 *  4   ||-------------Aux Count-------------|----------Num At Cur Min-----------|
 *
 *      ||   47   |   46   |   45   |   44   |   43   |   42   |   41   |   40   |
 *  5   ||...................................|------Start of HLL_X Byte Array----|
 *
 *  N   ||----End of Byte Array for HLL_4----|...................................|
 *  N+1 ||...................................|-----Start of Aux Array for HLL_4--|
 * </pre>
 * If in compact form exceptions array will be compacted.
 *
 * @author Lee Rhodes
 */
final class PreambleUtil {

  private PreambleUtil() {}

  // ###### DO NOT MESS WITH THIS ...
  // Preamble byte start addresses
  // First 8 Bytes:
  static int PREAMBLE_INTS_BYTE             = 0;
  static int SER_VER_BYTE                   = 1;
  static int FAMILY_BYTE                    = 2;
  static int LG_K_BYTE                      = 3;
  static int LG_ARR_BYTE                    = 4; //used for LIST, SET & HLL_4
  static int FLAGS_BYTE                     = 5;
  static int LIST_COUNT_BYTE                = 6;
  static int HLL_CUR_MIN_BYTE               = 6;
  static int MODE_BYTE                      = 7; //lo2bits = curMode, next 2 bits = tgtHllType
  //mode encoding of combined CurMode and TgtHllType:
  // Dec  Lo4Bits TgtHllType, CurMode
  //   0     0000      HLL_4,    LIST
  //   1     0001      HLL_4,     SET
  //   2     0010      HLL_4,     HLL
  //   4     0100      HLL_6,    LIST
  //   5     0101      HLL_6,     SET
  //   6     0110      HLL_6,     HLL
  //   8     1000      HLL_8,    LIST
  //   9     1001      HLL_8,     SET
  //  10     1010      HLL_8,     HLL

  //Coupon List
  static int LIST_INT_ARR_START             = 8;

  //Coupon Hash Set
  static int HASH_SET_COUNT_INT             = 8;
  static int HASH_SET_INT_ARR_START         = 12;

  //HLL
  static int HIP_ACCUM_DOUBLE               = 8;
  static int KXQ0_DOUBLE                    = 16;
  static int KXQ1_DOUBLE                    = 24;
  static int CUR_MIN_COUNT_INT              = 32;
  static int AUX_COUNT_INT                  = 36;
  static int HLL_BYTE_ARR_START             = 40;

  //Flag bit masks
  static final int BIG_ENDIAN_FLAG_MASK     = 1; //Set but not read. Reserved.
  static final int READ_ONLY_FLAG_MASK      = 2; //Set but not read. Reserved.
  static final int EMPTY_FLAG_MASK          = 4;
  static final int COMPACT_FLAG_MASK        = 8;
  static final int OUT_OF_ORDER_FLAG_MASK   = 16;
  static final int REBUILD_CURMIN_NUM_KXQ_MASK = 32; //used only by Union

  //Mode byte masks
  static final int CUR_MODE_MASK            = 3;
  static final int TGT_HLL_TYPE_MASK        = 12;

  //Other constants
  static final int SER_VER                  = 1;
  static final int FAMILY_ID                = 7;
  static final int LIST_PREINTS             = 2;
  static final int HASH_SET_PREINTS         = 3;
  static final int HLL_PREINTS              = 10;
  static final boolean NATIVE_ORDER_IS_BIG_ENDIAN  =
      (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN);

  static String toString(final byte[] byteArr) {
    final Memory mem = Memory.wrap(byteArr);
    return toString(mem);
  }

  static String toString(final Memory mem) {
    //First 8 bytes
    final int preInts = mem.getByte(PREAMBLE_INTS_BYTE);
    final int serVer = mem.getByte(SER_VER_BYTE);
    final Family family = Family.idToFamily(mem.getByte(FAMILY_BYTE));
    final int lgK = mem.getByte(LG_K_BYTE);
    final int lgArr = mem.getByte(LG_ARR_BYTE);
    final int flags = mem.getByte(FLAGS_BYTE);
    //Flags
    final String flagsStr = zeroPad(Integer.toBinaryString(flags), 8) + ", " + (flags);
    final boolean bigEndian = (flags & BIG_ENDIAN_FLAG_MASK) > 0;
    final String nativeOrder = ByteOrder.nativeOrder().toString();
    final boolean compact = (flags & COMPACT_FLAG_MASK) > 0;
    final boolean oooFlag = (flags & OUT_OF_ORDER_FLAG_MASK) > 0;
    final boolean readOnly = (flags & READ_ONLY_FLAG_MASK) > 0;
    final boolean empty = (flags & EMPTY_FLAG_MASK) > 0;
    final boolean rebuildKxQ = (flags & REBUILD_CURMIN_NUM_KXQ_MASK) > 0;

    final int hllCurMin = mem.getByte(HLL_CUR_MIN_BYTE);
    final int listCount = hllCurMin;
    final int modeByte = mem.getByte(MODE_BYTE);
    final CurMode curMode = CurMode.fromOrdinal(modeByte & 3);
    final TgtHllType tgtHllType = TgtHllType.fromOrdinal((modeByte >>> 2) & 3);

    double hipAccum = 0;
    double kxq0 = 0;
    double kxq1 = 0;
    int hashSetCount = 0;
    int curMinCount = 0;
    int exceptionCount = 0;

    if (curMode == CurMode.SET) {
      hashSetCount = mem.getInt(HASH_SET_COUNT_INT);
    }
    else if (curMode == CurMode.HLL) {
      hipAccum = mem.getDouble(HIP_ACCUM_DOUBLE);
      kxq0 = mem.getDouble(KXQ0_DOUBLE);
      kxq1 = mem.getDouble(KXQ1_DOUBLE);
      curMinCount = mem.getInt(CUR_MIN_COUNT_INT);
      exceptionCount = mem.getInt(AUX_COUNT_INT);
    }

    final StringBuilder sb = new StringBuilder();
    sb.append(LS);
    sb.append("### HLL SKETCH PREAMBLE:").append(LS);
    sb.append("Byte 0: Preamble Ints         : ").append(preInts).append(LS);
    sb.append("Byte 1: SerVer                : ").append(serVer).append(LS);
    sb.append("Byte 2: Family                : ").append(family).append(LS);
    sb.append("Byte 3: lgK                   : ").append(lgK).append(LS);
    //expand byte 4: LgArr
    if (curMode == CurMode.LIST) {
      sb.append("Byte 4: LgArr: List Arr       : ").append(lgArr).append(LS);
    }
    if (curMode == CurMode.SET) {
      sb.append("Byte 4: LgArr: Hash Set Arr   : ").append(lgArr).append(LS);
    }
    if (curMode == CurMode.HLL) {
      sb.append("Byte 4: LgArr or Aux LgArr    : ").append(lgArr).append(LS);
    }
    //expand byte 5: Flags
    sb.append("Byte 5: Flags:                : ").append(flagsStr).append(LS);
    sb.append("  BIG_ENDIAN_STORAGE          : ").append(bigEndian).append(LS);
    sb.append("  (Native Byte Order)         : ").append(nativeOrder).append(LS);
    sb.append("  READ_ONLY                   : ").append(readOnly).append(LS);
    sb.append("  EMPTY                       : ").append(empty).append(LS);
    sb.append("  COMPACT                     : ").append(compact).append(LS);
    sb.append("  OUT_OF_ORDER                : ").append(oooFlag).append(LS);
    sb.append("  REBUILD_KXQ                 : ").append(rebuildKxQ).append(LS);
    //expand byte 6: ListCount, CurMin
    if (curMode == CurMode.LIST) {
      sb.append("Byte 6: List Count/CurMin     : ").append(listCount).append(LS);
    }
    if (curMode == CurMode.SET) {
      sb.append("Byte 6: (not used)            : ").append(LS);
    }
    if (curMode == CurMode.HLL) {
      sb.append("Byte 6: Cur Min               : ").append(hllCurMin).append(LS);
    }
    final String modes = curMode.toString() + ", " + tgtHllType.toString();
    sb.append("Byte 7: Mode                  : ").append(modes).append(LS);
    if (curMode == CurMode.SET) {
      sb.append("Hash Set Count                : ").append(hashSetCount).append(LS);
    }
    if (curMode == CurMode.HLL) {
      sb.append("HIP Accum                     : ").append(hipAccum).append(LS);
      sb.append("KxQ0                          : ").append(kxq0).append(LS);
      sb.append("KxQ1                          : ").append(kxq1).append(LS);
      sb.append("Num At Cur Min                : ").append(curMinCount).append(LS);
      sb.append("Aux Count                     : ").append(exceptionCount).append(LS);
    }
    sb.append("### END HLL SKETCH PREAMBLE").append(LS);
    return sb.toString();
  }
  //@formatter:on

  static int extractPreInts(final Memory mem) {
    return mem.getByte(PREAMBLE_INTS_BYTE) & 0X3F;
  }

  static void insertPreInts(final WritableMemory wmem, final int preInts) {
    wmem.putByte(PREAMBLE_INTS_BYTE, (byte) (preInts & 0X3F));
  }

  static int extractSerVer(final Memory mem) {
    return mem.getByte(SER_VER_BYTE) & 0XFF;
  }

  static void insertSerVer(final WritableMemory wmem) {
    wmem.putByte(SER_VER_BYTE, (byte) SER_VER);
  }

  static int extractFamilyId(final Memory mem) {
    return mem.getByte(FAMILY_BYTE) & 0XFF;
  }

  static void insertFamilyId(final WritableMemory wmem) {
    wmem.putByte(FAMILY_BYTE, (byte) FAMILY_ID);
  }

  static int extractLgK(final Memory mem) {
    return mem.getByte(LG_K_BYTE) & 0XFF;
  }

  static void insertLgK(final WritableMemory wmem, final int lgK) {
    wmem.putByte(LG_K_BYTE, (byte) lgK);
  }

  static int extractLgArr(final Memory mem) {
    final int lgArr = mem.getByte(LG_ARR_BYTE) & 0XFF;
    return lgArr;
  }

  static void insertLgArr(final WritableMemory wmem, final int lgArr) {
    wmem.putByte(LG_ARR_BYTE, (byte) lgArr);
  }

  static int extractListCount(final Memory mem) {
    return mem.getByte(LIST_COUNT_BYTE) & 0XFF;
  }

  static void insertListCount(final WritableMemory wmem, final int listCnt) {
    wmem.putByte(LIST_COUNT_BYTE, (byte) listCnt);
  }

  static int extractCurMin(final Memory mem) {
    return mem.getByte(HLL_CUR_MIN_BYTE) & 0XFF;
  }

  static void insertCurMin(final WritableMemory wmem, final int curMin) {
    wmem.putByte(HLL_CUR_MIN_BYTE, (byte) curMin);
  }

  static double extractHipAccum(final Memory mem) {
    return mem.getDouble(HIP_ACCUM_DOUBLE);
  }

  static void insertHipAccum(final WritableMemory wmem, final double hipAccum) {
    wmem.putDouble(HIP_ACCUM_DOUBLE, hipAccum);
  }

  static double extractKxQ0(final Memory mem) {
    return mem.getDouble(KXQ0_DOUBLE);
  }

  static void insertKxQ0(final WritableMemory wmem, final double kxq0) {
    wmem.putDouble(KXQ0_DOUBLE, kxq0);
  }

  static double extractKxQ1(final Memory mem) {
    return mem.getDouble(KXQ1_DOUBLE);
  }

  static void insertKxQ1(final WritableMemory wmem, final double kxq1) {
    wmem.putDouble(KXQ1_DOUBLE, kxq1);
  }

  static int extractHashSetCount(final Memory mem) {
    return mem.getInt(HASH_SET_COUNT_INT);
  }

  static void insertHashSetCount(final WritableMemory wmem, final int hashSetCnt) {
    wmem.putInt(HASH_SET_COUNT_INT, hashSetCnt);
  }

  static int extractNumAtCurMin(final Memory mem) {
    return mem.getInt(CUR_MIN_COUNT_INT);
  }

  static void insertNumAtCurMin(final WritableMemory wmem, final int numAtCurMin) {
    wmem.putInt(CUR_MIN_COUNT_INT, numAtCurMin);
  }

  static int extractAuxCount(final Memory mem) {
    return mem.getInt(AUX_COUNT_INT);
  }

  static void insertAuxCount(final WritableMemory wmem, final int auxCount) {
    wmem.putInt(AUX_COUNT_INT, auxCount);
  }

  //Mode bits
  static void insertCurMode(final WritableMemory wmem, final CurMode curMode) {
    final int curModeId = curMode.ordinal();
    int mode = wmem.getByte(MODE_BYTE)  & ~CUR_MODE_MASK; //strip bits 0, 1
    mode |= (curModeId & CUR_MODE_MASK);
    wmem.putByte(MODE_BYTE, (byte) mode);
  }

  static CurMode extractCurMode(final Memory mem) {
    final int curModeId = mem.getByte(MODE_BYTE) & CUR_MODE_MASK;
    return CurMode.fromOrdinal(curModeId);
  }

  static void insertTgtHllType(final WritableMemory wmem, final TgtHllType tgtHllType) {
    final int typeId = tgtHllType.ordinal();
    int mode = wmem.getByte(MODE_BYTE) & ~TGT_HLL_TYPE_MASK; //strip bits 2, 3
    mode |= (typeId << 2) & TGT_HLL_TYPE_MASK;
    wmem.putByte(MODE_BYTE, (byte) mode);
  }

  static TgtHllType extractTgtHllType(final Memory mem) {
    final int typeId = mem.getByte(MODE_BYTE) & TGT_HLL_TYPE_MASK;
    return TgtHllType.fromOrdinal(typeId >>> 2);
  }

  static void insertModes(final WritableMemory wmem, final TgtHllType tgtHllType,
      final CurMode curMode) {
    final int curModeId = curMode.ordinal() & 3;
    final int typeId = (tgtHllType.ordinal() & 3) << 2;
    final int mode = typeId | curModeId;
    wmem.putByte(MODE_BYTE, (byte) mode);
  }

  //Flags
  static void insertEmptyFlag(final WritableMemory wmem, final boolean empty) {
    int flags = wmem.getByte(FLAGS_BYTE);
    if (empty) { flags |= EMPTY_FLAG_MASK; }
    else { flags &= ~EMPTY_FLAG_MASK; }
    wmem.putByte(FLAGS_BYTE, (byte) flags);
  }

  static boolean extractEmptyFlag(final Memory mem) {
    final int flags = mem.getByte(FLAGS_BYTE);
    return (flags & EMPTY_FLAG_MASK) > 0;
  }

  static void insertCompactFlag(final WritableMemory wmem, final boolean compact) {
    int flags = wmem.getByte(FLAGS_BYTE);
    if (compact) { flags |= COMPACT_FLAG_MASK; }
    else { flags &= ~COMPACT_FLAG_MASK; }
    wmem.putByte(FLAGS_BYTE, (byte) flags);
  }

  static boolean extractCompactFlag(final Memory mem) {
    final int flags = mem.getByte(FLAGS_BYTE);
    return (flags & COMPACT_FLAG_MASK) > 0;
  }

  static void insertOooFlag(final WritableMemory wmem, final boolean oooFlag) {
    int flags = wmem.getByte(FLAGS_BYTE);
    if (oooFlag) { flags |= OUT_OF_ORDER_FLAG_MASK; }
    else { flags &= ~OUT_OF_ORDER_FLAG_MASK; }
    wmem.putByte(FLAGS_BYTE, (byte) flags);
  }

  static boolean extractOooFlag(final Memory mem) {
    final int flags = mem.getByte(FLAGS_BYTE);
    return (flags & OUT_OF_ORDER_FLAG_MASK) > 0;
  }

  static void insertRebuildCurMinNumKxQFlag(final WritableMemory wmem, final boolean rebuild) {
    int flags = wmem.getByte(FLAGS_BYTE);
    if (rebuild) { flags |= REBUILD_CURMIN_NUM_KXQ_MASK; }
    else { flags &= ~REBUILD_CURMIN_NUM_KXQ_MASK; }
    wmem.putByte(FLAGS_BYTE, (byte) flags);
  }

  static boolean extractRebuildCurMinNumKxQFlag(final Memory mem) {
    final int flags = mem.getByte(FLAGS_BYTE);
    return (flags & REBUILD_CURMIN_NUM_KXQ_MASK) > 0;
  }

  static void insertFlags(final WritableMemory wmem, final int flags) {
    wmem.putByte(FLAGS_BYTE, (byte) flags);
  }

  static int extractFlags(final Memory mem) {
    return mem.getByte(FLAGS_BYTE) & 0XFF;
  }

  //Other
  static int extractInt(final Memory mem, final long byteOffset) {
    return mem.getInt(byteOffset);
  }

  static void insertInt(final WritableMemory wmem, final long byteOffset, final int value) {
    wmem.putInt(byteOffset, value);
  }

  static int computeLgArr(final Memory mem, final int count, final int lgConfigK) {
    //value is missing, recompute
    final CurMode curMode = extractCurMode(mem);
    if (curMode == CurMode.LIST) { return HllUtil.LG_INIT_LIST_SIZE; }
    int ceilPwr2 = ceilingPowerOf2(count);
    if ((RESIZE_DENOM * count) > (RESIZE_NUMER * ceilPwr2)) { ceilPwr2 <<= 1; }
    if (curMode == CurMode.SET) {
      return Math.max(LG_INIT_SET_SIZE, exactLog2OfLong(ceilPwr2));
    }
    //only used for HLL4
    return Math.max(LG_AUX_ARR_INTS[lgConfigK], exactLog2OfLong(ceilPwr2));
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.hll;
21
22	import static org.apache.datasketches.common.Util.LS;
23	import static org.apache.datasketches.common.Util.ceilingPowerOf2;
24	import static org.apache.datasketches.common.Util.exactLog2OfLong;
25	import static org.apache.datasketches.common.Util.zeroPad;
26	import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;
27	import static org.apache.datasketches.hll.HllUtil.LG_INIT_SET_SIZE;
28	import static org.apache.datasketches.hll.HllUtil.RESIZE_DENOM;
29	import static org.apache.datasketches.hll.HllUtil.RESIZE_NUMER;
30
31	import java.nio.ByteOrder;
32
33	import org.apache.datasketches.common.Family;
34	import org.apache.datasketches.memory.Memory;
35	import org.apache.datasketches.memory.WritableMemory;
36
37	//@formatter:off
38	/**
39	* <pre>
40	* CouponList Layout
41	* Long \|\| Start Byte Adr, Big Endian Illustration
42	* Adr:
43	* \|\| 7 \| 6 \| 5 \| 4 \| 3 \| 2 \| 1 \| 0 \|
44	* 0 \|\| Mode \| ListCnt\| Flags \| LgArr \| lgK \| FamID \| SerVer \| PI=2 \|
45	*
46	* \|\| 15 \| 14 \| 13 \| 12 \| 11 \| 10 \| 9 \| 8 \|
47	* 1 \|\| \|------Coupon Int List Start--------\|
48	* </pre>
49	*
50	* <pre>
51	* CouponHashSet Layout
52	* Long \|\| Start Byte Adr, Big Endian Illustration
53	* Adr:
54	* \|\| 7 \| 6 \| 5 \| 4 \| 3 \| 2 \| 1 \| 0 \|
55	* 0 \|\| Mode \| \| Flags \| LgArr \| lgK \| FamID \| SerVer \| PI=3 \|
56	*
57	* \|\| 15 \| 14 \| 13 \| 12 \| 11 \| 10 \| 9 \| 8 \|
58	* 1 \|\|-----Coupon Int Hash Set Start-----\|---------Hash Set Count------------\|
59	* </pre>
60	*
61	* <pre>
62	* HllArray Layout
63	* Long \|\| Start Byte Adr, Big Endian Illustration
64	* Adr:
65	* \|\| 7 \| 6 \| 5 \| 4 \| 3 \| 2 \| 1 \| 0 \|
66	* 0 \|\| Mode \| CurMin \| Flags \| LgArr \| lgK \| FamID \| SerVer \| PI=10 \|
67	*
68	* \|\| 15 \| 14 \| 13 \| 12 \| 11 \| 10 \| 9 \| 8 \|
69	* 1 \|\|-------------------------------HIP Accum-------------------------------\|
70	*
71	* \|\| 23 \| 22 \| 21 \| 20 \| 19 \| 18 \| 17 \| 16 \|
72	* 2 \|\|----------------------------------KxQ0---------------------------------\|
73	*
74	* \|\| 31 \| 30 \| 29 \| 28 \| 27 \| 26 \| 25 \| 24 \|
75	* 3 \|\|----------------------------------KxQ1---------------------------------\|
76	*
77	* \|\| 39 \| 38 \| 37 \| 36 \| 35 \| 34 \| 33 \| 32 \|
78	* 4 \|\|-------------Aux Count-------------\|----------Num At Cur Min-----------\|
79	*
80	* \|\| 47 \| 46 \| 45 \| 44 \| 43 \| 42 \| 41 \| 40 \|
81	* 5 \|\|...................................\|------Start of HLL_X Byte Array----\|
82	*
83	* N \|\|----End of Byte Array for HLL_4----\|...................................\|
84	* N+1 \|\|...................................\|-----Start of Aux Array for HLL_4--\|
85	* </pre>
86	* If in compact form exceptions array will be compacted.
87	*
88	* @author Lee Rhodes
89	*/
90	final class PreambleUtil {
91
92	private PreambleUtil() {}
93
94	// ###### DO NOT MESS WITH THIS ...
95	// Preamble byte start addresses
96	// First 8 Bytes:
97	static int PREAMBLE_INTS_BYTE = 0;	1✔
98	static int SER_VER_BYTE = 1;	1✔
99	static int FAMILY_BYTE = 2;	1✔
100	static int LG_K_BYTE = 3;	1✔
101	static int LG_ARR_BYTE = 4; //used for LIST, SET & HLL_4	1✔
102	static int FLAGS_BYTE = 5;	1✔
103	static int LIST_COUNT_BYTE = 6;	1✔
104	static int HLL_CUR_MIN_BYTE = 6;	1✔
105	static int MODE_BYTE = 7; //lo2bits = curMode, next 2 bits = tgtHllType	1✔
106	//mode encoding of combined CurMode and TgtHllType:
107	// Dec Lo4Bits TgtHllType, CurMode
108	// 0 0000 HLL_4, LIST
109	// 1 0001 HLL_4, SET
110	// 2 0010 HLL_4, HLL
111	// 4 0100 HLL_6, LIST
112	// 5 0101 HLL_6, SET
113	// 6 0110 HLL_6, HLL
114	// 8 1000 HLL_8, LIST
115	// 9 1001 HLL_8, SET
116	// 10 1010 HLL_8, HLL
117
118	//Coupon List
119	static int LIST_INT_ARR_START = 8;	1✔
120
121	//Coupon Hash Set
122	static int HASH_SET_COUNT_INT = 8;	1✔
123	static int HASH_SET_INT_ARR_START = 12;	1✔
124
125	//HLL
126	static int HIP_ACCUM_DOUBLE = 8;	1✔
127	static int KXQ0_DOUBLE = 16;	1✔
128	static int KXQ1_DOUBLE = 24;	1✔
129	static int CUR_MIN_COUNT_INT = 32;	1✔
130	static int AUX_COUNT_INT = 36;	1✔
131	static int HLL_BYTE_ARR_START = 40;	1✔
132
133	//Flag bit masks
134	static final int BIG_ENDIAN_FLAG_MASK = 1; //Set but not read. Reserved.
135	static final int READ_ONLY_FLAG_MASK = 2; //Set but not read. Reserved.
136	static final int EMPTY_FLAG_MASK = 4;
137	static final int COMPACT_FLAG_MASK = 8;
138	static final int OUT_OF_ORDER_FLAG_MASK = 16;
139	static final int REBUILD_CURMIN_NUM_KXQ_MASK = 32; //used only by Union
140
141	//Mode byte masks
142	static final int CUR_MODE_MASK = 3;
143	static final int TGT_HLL_TYPE_MASK = 12;
144
145	//Other constants
146	static final int SER_VER = 1;
147	static final int FAMILY_ID = 7;
148	static final int LIST_PREINTS = 2;
149	static final int HASH_SET_PREINTS = 3;
150	static final int HLL_PREINTS = 10;
151	static final boolean NATIVE_ORDER_IS_BIG_ENDIAN =	1✔
152	(ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN);	1✔
153
154	static String toString(final byte[] byteArr) {
155	final Memory mem = Memory.wrap(byteArr);	×
156	return toString(mem);	×
157	}
158
159	static String toString(final Memory mem) {
160	//First 8 bytes
161	final int preInts = mem.getByte(PREAMBLE_INTS_BYTE);	1✔
162	final int serVer = mem.getByte(SER_VER_BYTE);	1✔
163	final Family family = Family.idToFamily(mem.getByte(FAMILY_BYTE));	1✔
164	final int lgK = mem.getByte(LG_K_BYTE);	1✔
165	final int lgArr = mem.getByte(LG_ARR_BYTE);	1✔
166	final int flags = mem.getByte(FLAGS_BYTE);	1✔
167	//Flags
168	final String flagsStr = zeroPad(Integer.toBinaryString(flags), 8) + ", " + (flags);	1✔
169	final boolean bigEndian = (flags & BIG_ENDIAN_FLAG_MASK) > 0;	1✔
170	final String nativeOrder = ByteOrder.nativeOrder().toString();	1✔
171	final boolean compact = (flags & COMPACT_FLAG_MASK) > 0;	1✔
172	final boolean oooFlag = (flags & OUT_OF_ORDER_FLAG_MASK) > 0;	1✔
173	final boolean readOnly = (flags & READ_ONLY_FLAG_MASK) > 0;	1✔
174	final boolean empty = (flags & EMPTY_FLAG_MASK) > 0;	1✔
175	final boolean rebuildKxQ = (flags & REBUILD_CURMIN_NUM_KXQ_MASK) > 0;	1✔
176
177	final int hllCurMin = mem.getByte(HLL_CUR_MIN_BYTE);	1✔
178	final int listCount = hllCurMin;	1✔
179	final int modeByte = mem.getByte(MODE_BYTE);	1✔
180	final CurMode curMode = CurMode.fromOrdinal(modeByte & 3);	1✔
181	final TgtHllType tgtHllType = TgtHllType.fromOrdinal((modeByte >>> 2) & 3);	1✔
182
183	double hipAccum = 0;	1✔
184	double kxq0 = 0;	1✔
185	double kxq1 = 0;	1✔
186	int hashSetCount = 0;	1✔
187	int curMinCount = 0;	1✔
188	int exceptionCount = 0;	1✔
189
190	if (curMode == CurMode.SET) {	1✔
191	hashSetCount = mem.getInt(HASH_SET_COUNT_INT);	1✔
192	}
193	else if (curMode == CurMode.HLL) {	1✔
194	hipAccum = mem.getDouble(HIP_ACCUM_DOUBLE);	1✔
195	kxq0 = mem.getDouble(KXQ0_DOUBLE);	1✔
196	kxq1 = mem.getDouble(KXQ1_DOUBLE);	1✔
197	curMinCount = mem.getInt(CUR_MIN_COUNT_INT);	1✔
198	exceptionCount = mem.getInt(AUX_COUNT_INT);	1✔
199	}
200
201	final StringBuilder sb = new StringBuilder();	1✔
202	sb.append(LS);	1✔
203	sb.append("### HLL SKETCH PREAMBLE:").append(LS);	1✔
204	sb.append("Byte 0: Preamble Ints : ").append(preInts).append(LS);	1✔
205	sb.append("Byte 1: SerVer : ").append(serVer).append(LS);	1✔
206	sb.append("Byte 2: Family : ").append(family).append(LS);	1✔
207	sb.append("Byte 3: lgK : ").append(lgK).append(LS);	1✔
208	//expand byte 4: LgArr
209	if (curMode == CurMode.LIST) {	1✔
210	sb.append("Byte 4: LgArr: List Arr : ").append(lgArr).append(LS);	1✔
211	}
212	if (curMode == CurMode.SET) {	1✔
213	sb.append("Byte 4: LgArr: Hash Set Arr : ").append(lgArr).append(LS);	1✔
214	}
215	if (curMode == CurMode.HLL) {	1✔
216	sb.append("Byte 4: LgArr or Aux LgArr : ").append(lgArr).append(LS);	1✔
217	}
218	//expand byte 5: Flags
219	sb.append("Byte 5: Flags: : ").append(flagsStr).append(LS);	1✔
220	sb.append(" BIG_ENDIAN_STORAGE : ").append(bigEndian).append(LS);	1✔
221	sb.append(" (Native Byte Order) : ").append(nativeOrder).append(LS);	1✔
222	sb.append(" READ_ONLY : ").append(readOnly).append(LS);	1✔
223	sb.append(" EMPTY : ").append(empty).append(LS);	1✔
224	sb.append(" COMPACT : ").append(compact).append(LS);	1✔
225	sb.append(" OUT_OF_ORDER : ").append(oooFlag).append(LS);	1✔
226	sb.append(" REBUILD_KXQ : ").append(rebuildKxQ).append(LS);	1✔
227	//expand byte 6: ListCount, CurMin
228	if (curMode == CurMode.LIST) {	1✔
229	sb.append("Byte 6: List Count/CurMin : ").append(listCount).append(LS);	1✔
230	}
231	if (curMode == CurMode.SET) {	1✔
232	sb.append("Byte 6: (not used) : ").append(LS);	1✔
233	}
234	if (curMode == CurMode.HLL) {	1✔
235	sb.append("Byte 6: Cur Min : ").append(hllCurMin).append(LS);	1✔
236	}
237	final String modes = curMode.toString() + ", " + tgtHllType.toString();	1✔
238	sb.append("Byte 7: Mode : ").append(modes).append(LS);	1✔
239	if (curMode == CurMode.SET) {	1✔
240	sb.append("Hash Set Count : ").append(hashSetCount).append(LS);	1✔
241	}
242	if (curMode == CurMode.HLL) {	1✔
243	sb.append("HIP Accum : ").append(hipAccum).append(LS);	1✔
244	sb.append("KxQ0 : ").append(kxq0).append(LS);	1✔
245	sb.append("KxQ1 : ").append(kxq1).append(LS);	1✔
246	sb.append("Num At Cur Min : ").append(curMinCount).append(LS);	1✔
247	sb.append("Aux Count : ").append(exceptionCount).append(LS);	1✔
248	}
249	sb.append("### END HLL SKETCH PREAMBLE").append(LS);	1✔
250	return sb.toString();	1✔
251	}
252	//@formatter:on
253
254	static int extractPreInts(final Memory mem) {
255	return mem.getByte(PREAMBLE_INTS_BYTE) & 0X3F;	1✔
256	}
257
258	static void insertPreInts(final WritableMemory wmem, final int preInts) {
259	wmem.putByte(PREAMBLE_INTS_BYTE, (byte) (preInts & 0X3F));	1✔
260	}	1✔
261
262	static int extractSerVer(final Memory mem) {
263	return mem.getByte(SER_VER_BYTE) & 0XFF;	1✔
264	}
265
266	static void insertSerVer(final WritableMemory wmem) {
267	wmem.putByte(SER_VER_BYTE, (byte) SER_VER);	1✔
268	}	1✔
269
270	static int extractFamilyId(final Memory mem) {
271	return mem.getByte(FAMILY_BYTE) & 0XFF;	1✔
272	}
273
274	static void insertFamilyId(final WritableMemory wmem) {
275	wmem.putByte(FAMILY_BYTE, (byte) FAMILY_ID);	1✔
276	}	1✔
277
278	static int extractLgK(final Memory mem) {
279	return mem.getByte(LG_K_BYTE) & 0XFF;	1✔
280	}
281
282	static void insertLgK(final WritableMemory wmem, final int lgK) {
283	wmem.putByte(LG_K_BYTE, (byte) lgK);	1✔
284	}	1✔
285
286	static int extractLgArr(final Memory mem) {
287	final int lgArr = mem.getByte(LG_ARR_BYTE) & 0XFF;	1✔
288	return lgArr;	1✔
289	}
290
291	static void insertLgArr(final WritableMemory wmem, final int lgArr) {
292	wmem.putByte(LG_ARR_BYTE, (byte) lgArr);	1✔
293	}	1✔
294
295	static int extractListCount(final Memory mem) {
296	return mem.getByte(LIST_COUNT_BYTE) & 0XFF;	1✔
297	}
298
299	static void insertListCount(final WritableMemory wmem, final int listCnt) {
300	wmem.putByte(LIST_COUNT_BYTE, (byte) listCnt);	1✔
301	}	1✔
302
303	static int extractCurMin(final Memory mem) {
304	return mem.getByte(HLL_CUR_MIN_BYTE) & 0XFF;	1✔
305	}
306
307	static void insertCurMin(final WritableMemory wmem, final int curMin) {
308	wmem.putByte(HLL_CUR_MIN_BYTE, (byte) curMin);	1✔
309	}	1✔
310
311	static double extractHipAccum(final Memory mem) {
312	return mem.getDouble(HIP_ACCUM_DOUBLE);	1✔
313	}
314
315	static void insertHipAccum(final WritableMemory wmem, final double hipAccum) {
316	wmem.putDouble(HIP_ACCUM_DOUBLE, hipAccum);	1✔
317	}	1✔
318
319	static double extractKxQ0(final Memory mem) {
320	return mem.getDouble(KXQ0_DOUBLE);	1✔
321	}
322
323	static void insertKxQ0(final WritableMemory wmem, final double kxq0) {
324	wmem.putDouble(KXQ0_DOUBLE, kxq0);	1✔
325	}	1✔
326
327	static double extractKxQ1(final Memory mem) {
328	return mem.getDouble(KXQ1_DOUBLE);	1✔
329	}
330
331	static void insertKxQ1(final WritableMemory wmem, final double kxq1) {
332	wmem.putDouble(KXQ1_DOUBLE, kxq1);	1✔
333	}	1✔
334
335	static int extractHashSetCount(final Memory mem) {
336	return mem.getInt(HASH_SET_COUNT_INT);	1✔
337	}
338
339	static void insertHashSetCount(final WritableMemory wmem, final int hashSetCnt) {
340	wmem.putInt(HASH_SET_COUNT_INT, hashSetCnt);	1✔
341	}	1✔
342
343	static int extractNumAtCurMin(final Memory mem) {
344	return mem.getInt(CUR_MIN_COUNT_INT);	1✔
345	}
346
347	static void insertNumAtCurMin(final WritableMemory wmem, final int numAtCurMin) {
348	wmem.putInt(CUR_MIN_COUNT_INT, numAtCurMin);	1✔
349	}	1✔
350
351	static int extractAuxCount(final Memory mem) {
352	return mem.getInt(AUX_COUNT_INT);	1✔
353	}
354
355	static void insertAuxCount(final WritableMemory wmem, final int auxCount) {
356	wmem.putInt(AUX_COUNT_INT, auxCount);	1✔
357	}	1✔
358
359	//Mode bits
360	static void insertCurMode(final WritableMemory wmem, final CurMode curMode) {
361	final int curModeId = curMode.ordinal();	1✔
362	int mode = wmem.getByte(MODE_BYTE) & ~CUR_MODE_MASK; //strip bits 0, 1	1✔
363	mode \|= (curModeId & CUR_MODE_MASK);	1✔
364	wmem.putByte(MODE_BYTE, (byte) mode);	1✔
365	}	1✔
366
367	static CurMode extractCurMode(final Memory mem) {
368	final int curModeId = mem.getByte(MODE_BYTE) & CUR_MODE_MASK;	1✔
369	return CurMode.fromOrdinal(curModeId);	1✔
370	}
371
372	static void insertTgtHllType(final WritableMemory wmem, final TgtHllType tgtHllType) {
373	final int typeId = tgtHllType.ordinal();	1✔
374	int mode = wmem.getByte(MODE_BYTE) & ~TGT_HLL_TYPE_MASK; //strip bits 2, 3	1✔
375	mode \|= (typeId << 2) & TGT_HLL_TYPE_MASK;	1✔
376	wmem.putByte(MODE_BYTE, (byte) mode);	1✔
377	}	1✔
378
379	static TgtHllType extractTgtHllType(final Memory mem) {
380	final int typeId = mem.getByte(MODE_BYTE) & TGT_HLL_TYPE_MASK;	1✔
381	return TgtHllType.fromOrdinal(typeId >>> 2);	1✔
382	}
383
384	static void insertModes(final WritableMemory wmem, final TgtHllType tgtHllType,
385	final CurMode curMode) {
386	final int curModeId = curMode.ordinal() & 3;	1✔
387	final int typeId = (tgtHllType.ordinal() & 3) << 2;	1✔
388	final int mode = typeId \| curModeId;	1✔
389	wmem.putByte(MODE_BYTE, (byte) mode);	1✔
390	}	1✔
391
392	//Flags
393	static void insertEmptyFlag(final WritableMemory wmem, final boolean empty) {
394	int flags = wmem.getByte(FLAGS_BYTE);	1✔
395	if (empty) { flags \|= EMPTY_FLAG_MASK; }	1✔
396	else { flags &= ~EMPTY_FLAG_MASK; }	1✔
397	wmem.putByte(FLAGS_BYTE, (byte) flags);	1✔
398	}	1✔
399
400	static boolean extractEmptyFlag(final Memory mem) {
401	final int flags = mem.getByte(FLAGS_BYTE);	1✔
402	return (flags & EMPTY_FLAG_MASK) > 0;	1✔
403	}
404
405	static void insertCompactFlag(final WritableMemory wmem, final boolean compact) {
406	int flags = wmem.getByte(FLAGS_BYTE);	1✔
407	if (compact) { flags \|= COMPACT_FLAG_MASK; }	1✔
408	else { flags &= ~COMPACT_FLAG_MASK; }	1✔
409	wmem.putByte(FLAGS_BYTE, (byte) flags);	1✔
410	}	1✔
411
412	static boolean extractCompactFlag(final Memory mem) {
413	final int flags = mem.getByte(FLAGS_BYTE);	1✔
414	return (flags & COMPACT_FLAG_MASK) > 0;	1✔
415	}
416
417	static void insertOooFlag(final WritableMemory wmem, final boolean oooFlag) {
418	int flags = wmem.getByte(FLAGS_BYTE);	1✔
419	if (oooFlag) { flags \|= OUT_OF_ORDER_FLAG_MASK; }	1✔
420	else { flags &= ~OUT_OF_ORDER_FLAG_MASK; }	1✔
421	wmem.putByte(FLAGS_BYTE, (byte) flags);	1✔
422	}	1✔
423
424	static boolean extractOooFlag(final Memory mem) {
425	final int flags = mem.getByte(FLAGS_BYTE);	1✔
426	return (flags & OUT_OF_ORDER_FLAG_MASK) > 0;	1✔
427	}
428
429	static void insertRebuildCurMinNumKxQFlag(final WritableMemory wmem, final boolean rebuild) {
430	int flags = wmem.getByte(FLAGS_BYTE);	1✔
431	if (rebuild) { flags \|= REBUILD_CURMIN_NUM_KXQ_MASK; }	1✔
432	else { flags &= ~REBUILD_CURMIN_NUM_KXQ_MASK; }	1✔
433	wmem.putByte(FLAGS_BYTE, (byte) flags);	1✔
434	}	1✔
435
436	static boolean extractRebuildCurMinNumKxQFlag(final Memory mem) {
437	final int flags = mem.getByte(FLAGS_BYTE);	1✔
438	return (flags & REBUILD_CURMIN_NUM_KXQ_MASK) > 0;	1✔
439	}
440
441	static void insertFlags(final WritableMemory wmem, final int flags) {
442	wmem.putByte(FLAGS_BYTE, (byte) flags);	1✔
443	}	1✔
444
445	static int extractFlags(final Memory mem) {
446	return mem.getByte(FLAGS_BYTE) & 0XFF;	1✔
447	}
448
449	//Other
450	static int extractInt(final Memory mem, final long byteOffset) {
451	return mem.getInt(byteOffset);	1✔
452	}
453
454	static void insertInt(final WritableMemory wmem, final long byteOffset, final int value) {
455	wmem.putInt(byteOffset, value);	1✔
456	}	1✔
457
458	static int computeLgArr(final Memory mem, final int count, final int lgConfigK) {
459	//value is missing, recompute
460	final CurMode curMode = extractCurMode(mem);	1✔
461	if (curMode == CurMode.LIST) { return HllUtil.LG_INIT_LIST_SIZE; }	1✔
462	int ceilPwr2 = ceilingPowerOf2(count);	1✔
463	if ((RESIZE_DENOM * count) > (RESIZE_NUMER * ceilPwr2)) { ceilPwr2 <<= 1; }	1✔
464	if (curMode == CurMode.SET) {	1✔
465	return Math.max(LG_INIT_SET_SIZE, exactLog2OfLong(ceilPwr2));	1✔
466	}
467	//only used for HLL4
468	return Math.max(LG_AUX_ARR_INTS[lgConfigK], exactLog2OfLong(ceilPwr2));	1✔
469	}
470
471	}

apache / datasketches-java / #306

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous