#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

95.24

/src/main/java/org/apache/datasketches/kll/KllPreambleUtil.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.kll;

import static org.apache.datasketches.common.Family.idToFamily;
import static org.apache.datasketches.common.Util.LS;
import static org.apache.datasketches.common.Util.zeroPad;
import static org.apache.datasketches.kll.KllSketch.SketchStructure.COMPACT_FULL;
import static org.apache.datasketches.kll.KllSketch.SketchStructure.COMPACT_SINGLE;
import static org.apache.datasketches.kll.KllSketch.SketchStructure.UPDATABLE;
import static org.apache.datasketches.kll.KllSketch.SketchType.DOUBLES_SKETCH;
import static org.apache.datasketches.kll.KllSketch.SketchType.FLOATS_SKETCH;
import static org.apache.datasketches.kll.KllSketch.SketchType.ITEMS_SKETCH;

import java.util.Objects;

import org.apache.datasketches.common.ArrayOfItemsSerDe;
import org.apache.datasketches.common.Util;
import org.apache.datasketches.kll.KllSketch.SketchStructure;
import org.apache.datasketches.kll.KllSketch.SketchType;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;

/**
 * This class defines the serialized data structure and provides access methods for the preamble fields.
 *
 * <p>The intent of the design of this class was to isolate the detailed knowledge of the bit and
 * byte layout of the serialized form of the sketches derived from the base sketch classes into one place.
 * This allows the possibility of the introduction of different serialization
 * schemes with minimal impact on the rest of the library.</p>
 *
 * <h3>Visual Layout</h3>
 * The low significance bytes of the visual data structure below are on the left.
 * The multi-byte primitives are stored in native byte order.
 * The numeric <i>byte</i> and <i>short</i> fields are treated as unsigned.
 * The numeric <i>int</i> and <i>long</i> fields are treated as signed.
 *
 * <h3>Preamble Formats</h3>
 * The preamble has four formats:
 *
 * <ul>
 * <li>The serialized empty compact structure requires 8 bytes of preamble. It is not updatable.
 * It is identified by the <i>enum SketchStructure.COMPACT_EMPTY.</i></li>
 *
 * <li>The serialized, single-item compact structure requires 8 bytes of preamble, followed by the one item.
 * The size of this structure is 8 + itemSize bytes. It is not updatable.
 * It is identified by the <i>enum SketchStructure.COMPACT_SINGLE.</i></li>
 *
 * <li>A serialized, <i>n &gt; 1</i> compact structure requires 20 bytes of preamble (5 ints) followed by
 * four variable-sized fields. The details of these fields can be found in the code and are illustrated
 * in the table below.
 * The 5 int preamble is followed by the <i>levelsArr int[numLevels]</i> as bytes,
 * followed by the min and max values as bytes,
 * followed by a packed items data array as bytes. There is no free space in this structure.
 * It is not updatable.
 * It is identified by the <i>enum SketchStructure.COMPACT_FULL</i>.</li>
 *
 * <li>A serialized, <i>n &gt; 1</i> non-compact, updatable structure requires 20 bytes of preamble (5 ints).
 * This is followed by the LevelsArr int[NumLevels + 1], followed by the min and max values, and then
 * followed by an items data array that may include free space. It is updatable.
 * The details of these fields can be found in the code..
 * It is identified by the <i>enum SketchStructure.UPDATABLE</i>. This structure may not be implemented by
 * some sketches.</li>
 * </ul>
 *
 * <h3>Visual Layout</h3>
 * The fields in braces are those that can be variable in size.
 *
 * <pre>{@code
 * Serialized COMPACT_EMPTY sketch structure, Empty (8 bytes)
 * and COMPACT_SINGLE sketch structure, (single item) (8 + itemSize):
 * Int Adr:   Byte Adr ->
 *    0     ||       0      |   1    |   2   |   3    |
 *          | PreambleInts  | SerVer | FamID | Flags  |
 *
 *    1     ||       4      |   5    |   6   |   7    |
 *          ||-----------K-----------|   M   | unused |
 *
 *    2     ||       8      |
 *          ||{Single Item} ->
 *
 * Serialized COMPACT_FULL sketch structure, more than one item:
 * Int Adr:   Byte Adr ->
 *    0     ||       0      |   1    |   2   |   3    |
 *          || PreambleInts | SerVer | FamID | Flags  |
 *
 *    1     ||       4      |   5    |   6   |   7    |
 *          ||-----------K-----------|   M   | unused |
 *
 *   2,3    || 8  | 9  | 10 | 11 | 12 | 13 | 14 | 15  |
 *          ||-----------------N_LONG-----------------|
 *
 *    4     ||      16      |   17   |  18   |  19    |
 *          ||------Min K------------|NumLvls| unused |
 *
 *    5     ||     20       |
 *            { Levels Array }
 *            {   Min Item   }
 *            {   Max Item   }
 *            { Items Array  }
 *
 * Serialization Combinations for SerVer and PreambleInts
 * | Sketch Structure | SerVer         | PreInts          |
 * |------------------|----------------|------------------|
 * | Compact Empty    | Empty/Full (1) | Empty/Single (2) | ReadOnly, 8 byte Preamble, nothing else
 * | Compact Single   | Single (2)     | Empty/Single (2) | ReadOnly, 8 byte Preamble + Single Item
 * | Compact Full     | Empty/Full (1) | Full (5)         | ReadOnly, 20 Byte Preamble, Short LevelsArr, Retained Items
 * | Updatable        | Updatable (3)  | Full (5)         | Updatable, 20 Byte Preamble, Full LevelsArr, All Items
 * | ERROR            | Single (2)     | Full (5)         |
 * | ERROR            | Updatable (3)  | Empty/Single (2) |
 * }</pre>
 *
 *  @author Lee Rhodes
 */
final class KllPreambleUtil<T> {

  private KllPreambleUtil() {}

  // Preamble byte addresses
  static final int PREAMBLE_INTS_BYTE_ADR     = 0;
  static final int SER_VER_BYTE_ADR           = 1;
  static final int FAMILY_BYTE_ADR            = 2;
  static final int FLAGS_BYTE_ADR             = 3;
  static final int K_SHORT_ADR                = 4;  // to 5
  static final int M_BYTE_ADR                 = 6;
  //                                            7 is reserved for future use
  // SINGLE ITEM ONLY
  static final int DATA_START_ADR_SINGLE_ITEM = 8; //also ok for empty

  // MULTI-ITEM
  static final int N_LONG_ADR                 = 8;  // to 15
  static final int MIN_K_SHORT_ADR            = 16; // to 17
  static final int NUM_LEVELS_BYTE_ADR        = 18;

  //                                            19 is reserved for future use
  static final int DATA_START_ADR             = 20; // Full Sketch, not single item

  // Other static members
  static final byte SERIAL_VERSION_EMPTY_FULL  = 1; // Empty or full preamble, NOT single item format, NOT updatable
  static final byte SERIAL_VERSION_SINGLE      = 2; // only single-item format, NOT updatable
  static final byte SERIAL_VERSION_UPDATABLE   = 3; // PreInts=5, Full preamble + LevelsArr + min, max + empty space
  static final byte PREAMBLE_INTS_EMPTY_SINGLE = 2; // for empty or single item
  static final byte PREAMBLE_INTS_FULL         = 5; // Full preamble, not empty nor single item.
  static final byte KLL_FAMILY                 = 15;

  // Flag bit masks
  static final int EMPTY_BIT_MASK             = 1;
  static final int LEVEL_ZERO_SORTED_BIT_MASK = 2;
  static final int SINGLE_ITEM_BIT_MASK       = 4;

  /**
   * Returns a human readable string summary of the internal state of the given sketch byte array.
   * Used primarily in testing.
   *
   * @param byteArr the given sketch byte array.
   * @param includeData if true, includes detail of retained data.
   * @return the summary string.
   */
  static String toString(final byte[] byteArr, final SketchType sketchType, final boolean includeData) {
    final Memory mem = Memory.wrap(byteArr);
    return toString(mem, sketchType, includeData, null);
  }

  /**
   * Returns a human readable string summary of the internal state of the given sketch byte array.
   * Used primarily in testing.
   *
   * @param byteArr the given sketch byte array.
   * @param includeData if true, includes detail of retained data.
   * @param serDe the serialization/deserialization class, required for KllItemsSketch.
   * @return the summary string.
   */
  static String toString(final byte[] byteArr, final SketchType sketchType, final boolean includeData,
      final ArrayOfItemsSerDe<?> serDe) {
    final Memory mem = Memory.wrap(byteArr);
    return toString(mem, sketchType, includeData, serDe);
  }

  /**
   * Returns a human readable string summary of the internal state of the given Memory.
   * Used primarily in testing.
   *
   * @param mem the given Memory
   * @param includeData if true, includes detail of retained data.
   * @return the summary string.
   */
  static String toString(final Memory mem, final SketchType sketchType, final boolean includeData) {
    return toString(mem, sketchType, includeData, null);
  }

  /**
   * Returns a human readable string summary of the internal state of the given Memory.
   * Used primarily in testing.
   *
   * @param mem the given Memory
   * @param sketchType the sketch type: FLOATS_SKETCH, DOUBLES_SKETCH, or ITEMS_SKETCH.
   * @param includeData if true, includes detail of retained data.
   * @param serDe must be supplied for KllItemsSketch, otherwise can be null.
   * @return the summary string.
   */
  static <T> String toString(final Memory mem, final SketchType sketchType, final boolean includeData,
      final ArrayOfItemsSerDe<T> serDe) {
    if (sketchType == ITEMS_SKETCH) {
      Objects.requireNonNull(serDe, "SerDe parameter must not be null for ITEMS_SKETCH.");
    }
    final KllMemoryValidate memVal = new KllMemoryValidate(mem, sketchType, serDe);
    final SketchStructure myStructure = memVal.sketchStructure;
    final int flags = memVal.flags & 0XFF;
    final String flagsStr = (flags) + ", 0x" + (Integer.toHexString(flags)) + ", "
        + zeroPad(Integer.toBinaryString(flags), 8);
    final int preInts = memVal.preInts; //??
    //final boolean updatable = mySketchStructure == UPDATABLE;
    final boolean emptyFlag = memVal.emptyFlag;
    final int sketchBytes = memVal.sketchBytes;
    final int typeBytes = sketchType == DOUBLES_SKETCH ? Double.BYTES : Float.BYTES;
    final int familyID = getMemoryFamilyID(mem);
    final String famName = idToFamily(familyID).toString();

    final StringBuilder sb = new StringBuilder();
    sb.append(Util.LS).append("### KLL SKETCH MEMORY SUMMARY:").append(LS);
    sb.append("Sketch Type                          : ").append(sketchType.toString()).append(LS);
    sb.append("SketchStructure                      : ").append(myStructure.toString()).append(LS);
    sb.append("Byte   0       : Preamble Ints       : ").append(preInts).append(LS);
    sb.append("Byte   1       : SerVer              : ").append(memVal.serVer).append(LS);
    sb.append("Byte   2       : FamilyID            : ").append(memVal.familyID).append(LS);
    sb.append("               : FamilyName          : ").append(famName).append(LS);
    sb.append("Byte   3       : Flags Field         : ").append(flagsStr).append(LS);
    sb.append("            Bit: Flag Name           : ").append(LS);
    sb.append("              0: EMPTY               : ").append(emptyFlag).append(LS);
    sb.append("              1: LEVEL_ZERO_SORTED   : ").append(memVal.level0SortedFlag).append(LS);
    sb.append("Bytes  4-5     : K                   : ").append(memVal.k).append(LS);
    sb.append("Byte   6       : Min Level Cap, M    : ").append(memVal.m).append(LS);
    sb.append("Byte   7       : (Reserved)          : ").append(LS);

    final long n = memVal.n;
    final int minK = memVal.minK;
    final int numLevels = memVal.numLevels;
    final int[] levelsArr = memVal.levelsArr; //the full levels array
    final int retainedItems = levelsArr[numLevels] - levelsArr[0];

    if (myStructure == COMPACT_FULL || myStructure == UPDATABLE) {
      sb.append("Bytes  8-15    : N                   : ").append(n).append(LS);
      sb.append("Bytes 16-17    : MinK                : ").append(minK).append(LS);
      sb.append("Byte  18       : NumLevels           : ").append(numLevels).append(LS);
    }
    else { //COMPACT_EMPTY OR COMPACT_SINGLE
      sb.append("Assumed        : N                   : ").append(n).append(LS);
      sb.append("Assumed        : MinK                : ").append(minK).append(LS);
      sb.append("Assumed        : NumLevels           : ").append(numLevels).append(LS);
    }
    sb.append("PreambleBytes                        : ").append(preInts * Integer.BYTES).append(LS);
    sb.append("Sketch Bytes                         : ").append(sketchBytes).append(LS);
    sb.append("Memory Capacity Bytes                : ").append(mem.getCapacity()).append(LS);
    sb.append("### END KLL Sketch Memory Summary").append(LS);

    if (includeData) {
      sb.append(LS);
      sb.append("### START KLL DATA:").append(LS);
      int offsetBytes = 0;

      if (myStructure == UPDATABLE) {

        sb.append("LEVELS ARR:").append(LS);
        offsetBytes = DATA_START_ADR;
        for (int i = 0; i < numLevels + 1; i++) {
          sb.append(i + ", " + mem.getInt(offsetBytes)).append(LS);
          offsetBytes += Integer.BYTES;
        }

        sb.append("MIN/MAX:").append(LS);
        if (sketchType == DOUBLES_SKETCH) {
          sb.append(mem.getDouble(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
          sb.append(mem.getDouble(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
        } else if (sketchType == FLOATS_SKETCH) {
          sb.append(mem.getFloat(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
          sb.append(mem.getFloat(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
        } else { //ITEMS_SKETCH
          sb.append("<<<Updatable Structure is not suppported by ItemsSketch>>>").append(LS);
        }

        sb.append("ALL DATA (including free space)").append(LS);
        final int itemsSpace = (sketchBytes - offsetBytes) / typeBytes;
        if (sketchType == DOUBLES_SKETCH) {
          for (int i = 0; i < itemsSpace; i++) {
            sb.append(i + ", " + mem.getDouble(offsetBytes)).append(LS);
            offsetBytes += typeBytes;
          }
        } else if (sketchType == FLOATS_SKETCH) {
          for (int i = 0; i < itemsSpace; i++) {
            sb.append(mem.getFloat(offsetBytes)).append(LS);
            offsetBytes += typeBytes;
          }
        } else { //ITEMS_SKETCH
          sb.append("<<<Updatable Structure is not suppported by ItemsSketch>>>").append(LS);
        }

      } else if (myStructure == COMPACT_FULL) {

        sb.append("LEVELS ARR:").append(LS);
        offsetBytes = DATA_START_ADR;
        int j;
        for (j = 0; j < numLevels; j++) {
          sb.append(j + ", " + mem.getInt(offsetBytes)).append(LS);
          offsetBytes += Integer.BYTES;
        }
        sb.append(j + ", " + levelsArr[numLevels]);
        sb.append(" (Top level of Levels Array is absent in Memory)").append(LS);

        sb.append("MIN/MAX:").append(LS);
        if (sketchType == DOUBLES_SKETCH) {
          sb.append(mem.getDouble(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
          sb.append(mem.getDouble(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
        } else if (sketchType == FLOATS_SKETCH) {
          sb.append(mem.getFloat(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
          sb.append(mem.getFloat(offsetBytes)).append(LS);
          offsetBytes += typeBytes;
        } else {  //ITEMS_SKETCH
          sb.append(serDe.deserializeFromMemory(mem, offsetBytes, 1)[0]).append(LS);
          offsetBytes += serDe.sizeOf(mem, offsetBytes, 1);
          sb.append(serDe.deserializeFromMemory(mem, offsetBytes, 1)[0]).append(LS);
          offsetBytes += serDe.sizeOf(mem, offsetBytes, 1);
        }

        sb.append("RETAINED DATA").append(LS);
        final int itemSpace = (sketchBytes - offsetBytes) / typeBytes;
        if (sketchType == DOUBLES_SKETCH) {
          for (int i = 0; i < itemSpace; i++) {
            sb.append(i + ", " + mem.getDouble(offsetBytes)).append(LS);
            offsetBytes += typeBytes;
          }
        } else if (sketchType == FLOATS_SKETCH) {
          for (int i = 0; i < itemSpace; i++) {
            sb.append(i + ", " + mem.getFloat(offsetBytes)).append(LS);
            offsetBytes += typeBytes;
          }
        } else { //ITEMS_SKETCH
          final T[] itemsArr = serDe.deserializeFromMemory(mem, offsetBytes, retainedItems);
          for (int i = 0; i < itemsArr.length; i++) {
            sb.append(i + ", " + serDe.toString(itemsArr[i])).append(LS);
          }
          offsetBytes += serDe.sizeOf(mem, offsetBytes, retainedItems);
        }

      } else if (myStructure == COMPACT_SINGLE) {

          sb.append("SINGLE ITEM DATUM: "); //no LS
          if (sketchType == DOUBLES_SKETCH) {
            sb.append(mem.getDouble(DATA_START_ADR_SINGLE_ITEM)).append(LS);
          } else if (sketchType == FLOATS_SKETCH) {
            sb.append(mem.getFloat(DATA_START_ADR_SINGLE_ITEM)).append(LS);
          } else { //ITEMS_SKETCH
            sb.append(serDe.deserializeFromMemory(mem, DATA_START_ADR_SINGLE_ITEM, 1)[0]).append(LS);
          }

      } else { //COMPACT_EMPTY
        sb.append("EMPTY, NO DATA").append(LS);
      }
      sb.append("### END KLL DATA:").append(LS);
    }
    return sb.toString();
  }

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

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

  static SketchStructure getMemorySketchStructure(final Memory mem) {
    final int preInts = getMemoryPreInts(mem);
    final int serVer = getMemorySerVer(mem);
    final SketchStructure structure = KllSketch.SketchStructure.getSketchStructure(preInts, serVer);
    return structure;
  }

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

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

  static boolean getMemoryEmptyFlag(final Memory mem) {
    return (getMemoryFlags(mem) & EMPTY_BIT_MASK) != 0;
  }

  static boolean getMemoryLevelZeroSortedFlag(final Memory mem) {
    return (getMemoryFlags(mem) & LEVEL_ZERO_SORTED_BIT_MASK) != 0;
  }

  static int getMemoryK(final Memory mem) {
    return mem.getShort(K_SHORT_ADR) & 0XFFFF;
  }

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

  static long getMemoryN(final Memory mem) {
    return mem.getLong(N_LONG_ADR);
  }

  static int getMemoryMinK(final Memory mem) {
    return mem.getShort(MIN_K_SHORT_ADR) & 0XFFFF;
  }

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

  static void setMemoryPreInts(final WritableMemory wmem, final int numPreInts) {
    wmem.putByte(PREAMBLE_INTS_BYTE_ADR, (byte) numPreInts);
  }

  static void setMemorySerVer(final WritableMemory wmem, final int serVer) {
    wmem.putByte(SER_VER_BYTE_ADR, (byte) serVer);
  }

  static void setMemoryFamilyID(final WritableMemory wmem, final int famId) {
    wmem.putByte(FAMILY_BYTE_ADR, (byte) famId);
  }

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

  static void setMemoryEmptyFlag(final WritableMemory wmem,  final boolean empty) {
    final int flags = getMemoryFlags(wmem);
    setMemoryFlags(wmem, empty ? flags | EMPTY_BIT_MASK : flags & ~EMPTY_BIT_MASK);
  }

  static void setMemoryLevelZeroSortedFlag(final WritableMemory wmem,  final boolean levelZeroSorted) {
    final int flags = getMemoryFlags(wmem);
    setMemoryFlags(wmem, levelZeroSorted ? flags | LEVEL_ZERO_SORTED_BIT_MASK : flags & ~LEVEL_ZERO_SORTED_BIT_MASK);
  }

  static void setMemoryK(final WritableMemory wmem, final int memK) {
    wmem.putShort(K_SHORT_ADR, (short) memK);
  }

  static void setMemoryM(final WritableMemory wmem, final int memM) {
    wmem.putByte(M_BYTE_ADR, (byte) memM);
  }

  static void setMemoryN(final WritableMemory wmem, final long memN) {
    wmem.putLong(N_LONG_ADR, memN);
  }

  static void setMemoryMinK(final WritableMemory wmem, final int memMinK) {
    wmem.putShort(MIN_K_SHORT_ADR, (short) memMinK);
  }

  static void setMemoryNumLevels(final WritableMemory wmem, final int memNumLevels) {
    wmem.putByte(NUM_LEVELS_BYTE_ADR, (byte) memNumLevels);
  }

}

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.kll;
21
22	import static org.apache.datasketches.common.Family.idToFamily;
23	import static org.apache.datasketches.common.Util.LS;
24	import static org.apache.datasketches.common.Util.zeroPad;
25	import static org.apache.datasketches.kll.KllSketch.SketchStructure.COMPACT_FULL;
26	import static org.apache.datasketches.kll.KllSketch.SketchStructure.COMPACT_SINGLE;
27	import static org.apache.datasketches.kll.KllSketch.SketchStructure.UPDATABLE;
28	import static org.apache.datasketches.kll.KllSketch.SketchType.DOUBLES_SKETCH;
29	import static org.apache.datasketches.kll.KllSketch.SketchType.FLOATS_SKETCH;
30	import static org.apache.datasketches.kll.KllSketch.SketchType.ITEMS_SKETCH;
31
32	import java.util.Objects;
33
34	import org.apache.datasketches.common.ArrayOfItemsSerDe;
35	import org.apache.datasketches.common.Util;
36	import org.apache.datasketches.kll.KllSketch.SketchStructure;
37	import org.apache.datasketches.kll.KllSketch.SketchType;
38	import org.apache.datasketches.memory.Memory;
39	import org.apache.datasketches.memory.WritableMemory;
40
41	/**
42	* This class defines the serialized data structure and provides access methods for the preamble fields.
43	*
44	* <p>The intent of the design of this class was to isolate the detailed knowledge of the bit and
45	* byte layout of the serialized form of the sketches derived from the base sketch classes into one place.
46	* This allows the possibility of the introduction of different serialization
47	* schemes with minimal impact on the rest of the library.</p>
48	*
49	* <h3>Visual Layout</h3>
50	* The low significance bytes of the visual data structure below are on the left.
51	* The multi-byte primitives are stored in native byte order.
52	* The numeric <i>byte</i> and <i>short</i> fields are treated as unsigned.
53	* The numeric <i>int</i> and <i>long</i> fields are treated as signed.
54	*
55	* <h3>Preamble Formats</h3>
56	* The preamble has four formats:
57	*
58	* <ul>
59	* <li>The serialized empty compact structure requires 8 bytes of preamble. It is not updatable.
60	* It is identified by the <i>enum SketchStructure.COMPACT_EMPTY.</i></li>
61	*
62	* <li>The serialized, single-item compact structure requires 8 bytes of preamble, followed by the one item.
63	* The size of this structure is 8 + itemSize bytes. It is not updatable.
64	* It is identified by the <i>enum SketchStructure.COMPACT_SINGLE.</i></li>
65	*
66	* <li>A serialized, <i>n > 1</i> compact structure requires 20 bytes of preamble (5 ints) followed by
67	* four variable-sized fields. The details of these fields can be found in the code and are illustrated
68	* in the table below.
69	* The 5 int preamble is followed by the <i>levelsArr int[numLevels]</i> as bytes,
70	* followed by the min and max values as bytes,
71	* followed by a packed items data array as bytes. There is no free space in this structure.
72	* It is not updatable.
73	* It is identified by the <i>enum SketchStructure.COMPACT_FULL</i>.</li>
74	*
75	* <li>A serialized, <i>n > 1</i> non-compact, updatable structure requires 20 bytes of preamble (5 ints).
76	* This is followed by the LevelsArr int[NumLevels + 1], followed by the min and max values, and then
77	* followed by an items data array that may include free space. It is updatable.
78	* The details of these fields can be found in the code..
79	* It is identified by the <i>enum SketchStructure.UPDATABLE</i>. This structure may not be implemented by
80	* some sketches.</li>
81	* </ul>
82	*
83	* <h3>Visual Layout</h3>
84	* The fields in braces are those that can be variable in size.
85	*
86	* <pre>{@code
87	* Serialized COMPACT_EMPTY sketch structure, Empty (8 bytes)
88	* and COMPACT_SINGLE sketch structure, (single item) (8 + itemSize):
89	* Int Adr: Byte Adr ->
90	* 0 \|\| 0 \| 1 \| 2 \| 3 \|
91	* \| PreambleInts \| SerVer \| FamID \| Flags \|
92	*
93	* 1 \|\| 4 \| 5 \| 6 \| 7 \|
94	* \|\|-----------K-----------\| M \| unused \|
95	*
96	* 2 \|\| 8 \|
97	* \|\|{Single Item} ->
98	*
99	* Serialized COMPACT_FULL sketch structure, more than one item:
100	* Int Adr: Byte Adr ->
101	* 0 \|\| 0 \| 1 \| 2 \| 3 \|
102	* \|\| PreambleInts \| SerVer \| FamID \| Flags \|
103	*
104	* 1 \|\| 4 \| 5 \| 6 \| 7 \|
105	* \|\|-----------K-----------\| M \| unused \|
106	*
107	* 2,3 \|\| 8 \| 9 \| 10 \| 11 \| 12 \| 13 \| 14 \| 15 \|
108	* \|\|-----------------N_LONG-----------------\|
109	*
110	* 4 \|\| 16 \| 17 \| 18 \| 19 \|
111	* \|\|------Min K------------\|NumLvls\| unused \|
112	*
113	* 5 \|\| 20 \|
114	* { Levels Array }
115	* { Min Item }
116	* { Max Item }
117	* { Items Array }
118	*
119	* Serialization Combinations for SerVer and PreambleInts
120	* \| Sketch Structure \| SerVer \| PreInts \|
121	* \|------------------\|----------------\|------------------\|
122	* \| Compact Empty \| Empty/Full (1) \| Empty/Single (2) \| ReadOnly, 8 byte Preamble, nothing else
123	* \| Compact Single \| Single (2) \| Empty/Single (2) \| ReadOnly, 8 byte Preamble + Single Item
124	* \| Compact Full \| Empty/Full (1) \| Full (5) \| ReadOnly, 20 Byte Preamble, Short LevelsArr, Retained Items
125	* \| Updatable \| Updatable (3) \| Full (5) \| Updatable, 20 Byte Preamble, Full LevelsArr, All Items
126	* \| ERROR \| Single (2) \| Full (5) \|
127	* \| ERROR \| Updatable (3) \| Empty/Single (2) \|
128	* }</pre>
129	*
130	* @author Lee Rhodes
131	*/
132	final class KllPreambleUtil<T> {
133
134	private KllPreambleUtil() {}
135
136	// Preamble byte addresses
137	static final int PREAMBLE_INTS_BYTE_ADR = 0;
138	static final int SER_VER_BYTE_ADR = 1;
139	static final int FAMILY_BYTE_ADR = 2;
140	static final int FLAGS_BYTE_ADR = 3;
141	static final int K_SHORT_ADR = 4; // to 5
142	static final int M_BYTE_ADR = 6;
143	// 7 is reserved for future use
144	// SINGLE ITEM ONLY
145	static final int DATA_START_ADR_SINGLE_ITEM = 8; //also ok for empty
146
147	// MULTI-ITEM
148	static final int N_LONG_ADR = 8; // to 15
149	static final int MIN_K_SHORT_ADR = 16; // to 17
150	static final int NUM_LEVELS_BYTE_ADR = 18;
151
152	// 19 is reserved for future use
153	static final int DATA_START_ADR = 20; // Full Sketch, not single item
154
155	// Other static members
156	static final byte SERIAL_VERSION_EMPTY_FULL = 1; // Empty or full preamble, NOT single item format, NOT updatable
157	static final byte SERIAL_VERSION_SINGLE = 2; // only single-item format, NOT updatable
158	static final byte SERIAL_VERSION_UPDATABLE = 3; // PreInts=5, Full preamble + LevelsArr + min, max + empty space
159	static final byte PREAMBLE_INTS_EMPTY_SINGLE = 2; // for empty or single item
160	static final byte PREAMBLE_INTS_FULL = 5; // Full preamble, not empty nor single item.
161	static final byte KLL_FAMILY = 15;
162
163	// Flag bit masks
164	static final int EMPTY_BIT_MASK = 1;
165	static final int LEVEL_ZERO_SORTED_BIT_MASK = 2;
166	static final int SINGLE_ITEM_BIT_MASK = 4;
167
168	/**
169	* Returns a human readable string summary of the internal state of the given sketch byte array.
170	* Used primarily in testing.
171	*
172	* @param byteArr the given sketch byte array.
173	* @param includeData if true, includes detail of retained data.
174	* @return the summary string.
175	*/
176	static String toString(final byte[] byteArr, final SketchType sketchType, final boolean includeData) {
177	final Memory mem = Memory.wrap(byteArr);	1✔
178	return toString(mem, sketchType, includeData, null);	1✔
179	}
180
181	/**
182	* Returns a human readable string summary of the internal state of the given sketch byte array.
183	* Used primarily in testing.
184	*
185	* @param byteArr the given sketch byte array.
186	* @param includeData if true, includes detail of retained data.
187	* @param serDe the serialization/deserialization class, required for KllItemsSketch.
188	* @return the summary string.
189	*/
190	static String toString(final byte[] byteArr, final SketchType sketchType, final boolean includeData,
191	final ArrayOfItemsSerDe<?> serDe) {
192	final Memory mem = Memory.wrap(byteArr);	×
193	return toString(mem, sketchType, includeData, serDe);	×
194	}
195
196	/**
197	* Returns a human readable string summary of the internal state of the given Memory.
198	* Used primarily in testing.
199	*
200	* @param mem the given Memory
201	* @param includeData if true, includes detail of retained data.
202	* @return the summary string.
203	*/
204	static String toString(final Memory mem, final SketchType sketchType, final boolean includeData) {
205	return toString(mem, sketchType, includeData, null);	1✔
206	}
207
208	/**
209	* Returns a human readable string summary of the internal state of the given Memory.
210	* Used primarily in testing.
211	*
212	* @param mem the given Memory
213	* @param sketchType the sketch type: FLOATS_SKETCH, DOUBLES_SKETCH, or ITEMS_SKETCH.
214	* @param includeData if true, includes detail of retained data.
215	* @param serDe must be supplied for KllItemsSketch, otherwise can be null.
216	* @return the summary string.
217	*/
218	static <T> String toString(final Memory mem, final SketchType sketchType, final boolean includeData,
219	final ArrayOfItemsSerDe<T> serDe) {
220	if (sketchType == ITEMS_SKETCH) {	1✔
221	Objects.requireNonNull(serDe, "SerDe parameter must not be null for ITEMS_SKETCH.");	1✔
222	}
223	final KllMemoryValidate memVal = new KllMemoryValidate(mem, sketchType, serDe);	1✔
224	final SketchStructure myStructure = memVal.sketchStructure;	1✔
225	final int flags = memVal.flags & 0XFF;	1✔
226	final String flagsStr = (flags) + ", 0x" + (Integer.toHexString(flags)) + ", "	1✔
227	+ zeroPad(Integer.toBinaryString(flags), 8);	1✔
228	final int preInts = memVal.preInts; //??	1✔
229	//final boolean updatable = mySketchStructure == UPDATABLE;
230	final boolean emptyFlag = memVal.emptyFlag;	1✔
231	final int sketchBytes = memVal.sketchBytes;	1✔
232	final int typeBytes = sketchType == DOUBLES_SKETCH ? Double.BYTES : Float.BYTES;	1✔
233	final int familyID = getMemoryFamilyID(mem);	1✔
234	final String famName = idToFamily(familyID).toString();	1✔
235
236	final StringBuilder sb = new StringBuilder();	1✔
237	sb.append(Util.LS).append("### KLL SKETCH MEMORY SUMMARY:").append(LS);	1✔
238	sb.append("Sketch Type : ").append(sketchType.toString()).append(LS);	1✔
239	sb.append("SketchStructure : ").append(myStructure.toString()).append(LS);	1✔
240	sb.append("Byte 0 : Preamble Ints : ").append(preInts).append(LS);	1✔
241	sb.append("Byte 1 : SerVer : ").append(memVal.serVer).append(LS);	1✔
242	sb.append("Byte 2 : FamilyID : ").append(memVal.familyID).append(LS);	1✔
243	sb.append(" : FamilyName : ").append(famName).append(LS);	1✔
244	sb.append("Byte 3 : Flags Field : ").append(flagsStr).append(LS);	1✔
245	sb.append(" Bit: Flag Name : ").append(LS);	1✔
246	sb.append(" 0: EMPTY : ").append(emptyFlag).append(LS);	1✔
247	sb.append(" 1: LEVEL_ZERO_SORTED : ").append(memVal.level0SortedFlag).append(LS);	1✔
248	sb.append("Bytes 4-5 : K : ").append(memVal.k).append(LS);	1✔
249	sb.append("Byte 6 : Min Level Cap, M : ").append(memVal.m).append(LS);	1✔
250	sb.append("Byte 7 : (Reserved) : ").append(LS);	1✔
251
252	final long n = memVal.n;	1✔
253	final int minK = memVal.minK;	1✔
254	final int numLevels = memVal.numLevels;	1✔
255	final int[] levelsArr = memVal.levelsArr; //the full levels array	1✔
256	final int retainedItems = levelsArr[numLevels] - levelsArr[0];	1✔
257
258	if (myStructure == COMPACT_FULL \|\| myStructure == UPDATABLE) {	1✔
259	sb.append("Bytes 8-15 : N : ").append(n).append(LS);	1✔
260	sb.append("Bytes 16-17 : MinK : ").append(minK).append(LS);	1✔
261	sb.append("Byte 18 : NumLevels : ").append(numLevels).append(LS);	1✔
262	}
263	else { //COMPACT_EMPTY OR COMPACT_SINGLE
264	sb.append("Assumed : N : ").append(n).append(LS);	1✔
265	sb.append("Assumed : MinK : ").append(minK).append(LS);	1✔
266	sb.append("Assumed : NumLevels : ").append(numLevels).append(LS);	1✔
267	}
268	sb.append("PreambleBytes : ").append(preInts * Integer.BYTES).append(LS);	1✔
269	sb.append("Sketch Bytes : ").append(sketchBytes).append(LS);	1✔
270	sb.append("Memory Capacity Bytes : ").append(mem.getCapacity()).append(LS);	1✔
271	sb.append("### END KLL Sketch Memory Summary").append(LS);	1✔
272
273	if (includeData) {	1✔
274	sb.append(LS);	1✔
275	sb.append("### START KLL DATA:").append(LS);	1✔
276	int offsetBytes = 0;	1✔
277
278	if (myStructure == UPDATABLE) {	1✔
279
280	sb.append("LEVELS ARR:").append(LS);	1✔
281	offsetBytes = DATA_START_ADR;	1✔
282	for (int i = 0; i < numLevels + 1; i++) {	1✔
283	sb.append(i + ", " + mem.getInt(offsetBytes)).append(LS);	1✔
284	offsetBytes += Integer.BYTES;	1✔
285	}
286
287	sb.append("MIN/MAX:").append(LS);	1✔
288	if (sketchType == DOUBLES_SKETCH) {	1✔
289	sb.append(mem.getDouble(offsetBytes)).append(LS);	1✔
290	offsetBytes += typeBytes;	1✔
291	sb.append(mem.getDouble(offsetBytes)).append(LS);	1✔
292	offsetBytes += typeBytes;	1✔
293	} else if (sketchType == FLOATS_SKETCH) {	1✔
294	sb.append(mem.getFloat(offsetBytes)).append(LS);	1✔
295	offsetBytes += typeBytes;	1✔
296	sb.append(mem.getFloat(offsetBytes)).append(LS);	1✔
297	offsetBytes += typeBytes;	1✔
298	} else { //ITEMS_SKETCH
299	sb.append("<<<Updatable Structure is not suppported by ItemsSketch>>>").append(LS);	×
300	}
301
302	sb.append("ALL DATA (including free space)").append(LS);	1✔
303	final int itemsSpace = (sketchBytes - offsetBytes) / typeBytes;	1✔
304	if (sketchType == DOUBLES_SKETCH) {	1✔
305	for (int i = 0; i < itemsSpace; i++) {	1✔
306	sb.append(i + ", " + mem.getDouble(offsetBytes)).append(LS);	1✔
307	offsetBytes += typeBytes;	1✔
308	}
309	} else if (sketchType == FLOATS_SKETCH) {	1✔
310	for (int i = 0; i < itemsSpace; i++) {	1✔
311	sb.append(mem.getFloat(offsetBytes)).append(LS);	1✔
312	offsetBytes += typeBytes;	1✔
313	}
314	} else { //ITEMS_SKETCH
315	sb.append("<<<Updatable Structure is not suppported by ItemsSketch>>>").append(LS);	×
316	}
317
318	} else if (myStructure == COMPACT_FULL) {	1✔
319
320	sb.append("LEVELS ARR:").append(LS);	1✔
321	offsetBytes = DATA_START_ADR;	1✔
322	int j;
323	for (j = 0; j < numLevels; j++) {	1✔
324	sb.append(j + ", " + mem.getInt(offsetBytes)).append(LS);	1✔
325	offsetBytes += Integer.BYTES;	1✔
326	}
327	sb.append(j + ", " + levelsArr[numLevels]);	1✔
328	sb.append(" (Top level of Levels Array is absent in Memory)").append(LS);	1✔
329
330	sb.append("MIN/MAX:").append(LS);	1✔
331	if (sketchType == DOUBLES_SKETCH) {	1✔
332	sb.append(mem.getDouble(offsetBytes)).append(LS);	1✔
333	offsetBytes += typeBytes;	1✔
334	sb.append(mem.getDouble(offsetBytes)).append(LS);	1✔
335	offsetBytes += typeBytes;	1✔
336	} else if (sketchType == FLOATS_SKETCH) {	1✔
337	sb.append(mem.getFloat(offsetBytes)).append(LS);	1✔
338	offsetBytes += typeBytes;	1✔
339	sb.append(mem.getFloat(offsetBytes)).append(LS);	1✔
340	offsetBytes += typeBytes;	1✔
341	} else { //ITEMS_SKETCH
342	sb.append(serDe.deserializeFromMemory(mem, offsetBytes, 1)[0]).append(LS);	1✔
343	offsetBytes += serDe.sizeOf(mem, offsetBytes, 1);	1✔
344	sb.append(serDe.deserializeFromMemory(mem, offsetBytes, 1)[0]).append(LS);	1✔
345	offsetBytes += serDe.sizeOf(mem, offsetBytes, 1);	1✔
346	}
347
348	sb.append("RETAINED DATA").append(LS);	1✔
349	final int itemSpace = (sketchBytes - offsetBytes) / typeBytes;	1✔
350	if (sketchType == DOUBLES_SKETCH) {	1✔
351	for (int i = 0; i < itemSpace; i++) {	1✔
352	sb.append(i + ", " + mem.getDouble(offsetBytes)).append(LS);	1✔
353	offsetBytes += typeBytes;	1✔
354	}
355	} else if (sketchType == FLOATS_SKETCH) {	1✔
356	for (int i = 0; i < itemSpace; i++) {	1✔
357	sb.append(i + ", " + mem.getFloat(offsetBytes)).append(LS);	1✔
358	offsetBytes += typeBytes;	1✔
359	}
360	} else { //ITEMS_SKETCH
361	final T[] itemsArr = serDe.deserializeFromMemory(mem, offsetBytes, retainedItems);	1✔
362	for (int i = 0; i < itemsArr.length; i++) {	1✔
363	sb.append(i + ", " + serDe.toString(itemsArr[i])).append(LS);	1✔
364	}
365	offsetBytes += serDe.sizeOf(mem, offsetBytes, retainedItems);	1✔
366	}
367
368	} else if (myStructure == COMPACT_SINGLE) {	1✔
369
370	sb.append("SINGLE ITEM DATUM: "); //no LS	1✔
371	if (sketchType == DOUBLES_SKETCH) {	1✔
372	sb.append(mem.getDouble(DATA_START_ADR_SINGLE_ITEM)).append(LS);	1✔
373	} else if (sketchType == FLOATS_SKETCH) {	1✔
374	sb.append(mem.getFloat(DATA_START_ADR_SINGLE_ITEM)).append(LS);	1✔
375	} else { //ITEMS_SKETCH
376	sb.append(serDe.deserializeFromMemory(mem, DATA_START_ADR_SINGLE_ITEM, 1)[0]).append(LS);	1✔
377	}
378
379	} else { //COMPACT_EMPTY
380	sb.append("EMPTY, NO DATA").append(LS);	1✔
381	}
382	sb.append("### END KLL DATA:").append(LS);	1✔
383	}
384	return sb.toString();	1✔
385	}
386
387	static int getMemoryPreInts(final Memory mem) {
388	return mem.getByte(PREAMBLE_INTS_BYTE_ADR) & 0XFF;	1✔
389	}
390
391	static int getMemorySerVer(final Memory mem) {
392	return mem.getByte(SER_VER_BYTE_ADR) & 0XFF;	1✔
393	}
394
395	static SketchStructure getMemorySketchStructure(final Memory mem) {
396	final int preInts = getMemoryPreInts(mem);	×
397	final int serVer = getMemorySerVer(mem);	×
398	final SketchStructure structure = KllSketch.SketchStructure.getSketchStructure(preInts, serVer);	×
399	return structure;	×
400	}
401
402	static int getMemoryFamilyID(final Memory mem) {
403	return mem.getByte(FAMILY_BYTE_ADR) & 0XFF;	1✔
404	}
405
406	static int getMemoryFlags(final Memory mem) {
407	return mem.getByte(FLAGS_BYTE_ADR) & 0XFF;	1✔
408	}
409
410	static boolean getMemoryEmptyFlag(final Memory mem) {
411	return (getMemoryFlags(mem) & EMPTY_BIT_MASK) != 0;	1✔
412	}
413
414	static boolean getMemoryLevelZeroSortedFlag(final Memory mem) {
415	return (getMemoryFlags(mem) & LEVEL_ZERO_SORTED_BIT_MASK) != 0;	1✔
416	}
417
418	static int getMemoryK(final Memory mem) {
419	return mem.getShort(K_SHORT_ADR) & 0XFFFF;	1✔
420	}
421
422	static int getMemoryM(final Memory mem) {
423	return mem.getByte(M_BYTE_ADR) & 0XFF;	1✔
424	}
425
426	static long getMemoryN(final Memory mem) {
427	return mem.getLong(N_LONG_ADR);	1✔
428	}
429
430	static int getMemoryMinK(final Memory mem) {
431	return mem.getShort(MIN_K_SHORT_ADR) & 0XFFFF;	1✔
432	}
433
434	static int getMemoryNumLevels(final Memory mem) {
435	return mem.getByte(NUM_LEVELS_BYTE_ADR) & 0XFF;	1✔
436	}
437
438	static void setMemoryPreInts(final WritableMemory wmem, final int numPreInts) {
439	wmem.putByte(PREAMBLE_INTS_BYTE_ADR, (byte) numPreInts);	1✔
440	}	1✔
441
442	static void setMemorySerVer(final WritableMemory wmem, final int serVer) {
443	wmem.putByte(SER_VER_BYTE_ADR, (byte) serVer);	1✔
444	}	1✔
445
446	static void setMemoryFamilyID(final WritableMemory wmem, final int famId) {
447	wmem.putByte(FAMILY_BYTE_ADR, (byte) famId);	1✔
448	}	1✔
449
450	static void setMemoryFlags(final WritableMemory wmem, final int flags) {
451	wmem.putByte(FLAGS_BYTE_ADR, (byte) flags);	1✔
452	}	1✔
453
454	static void setMemoryEmptyFlag(final WritableMemory wmem, final boolean empty) {
455	final int flags = getMemoryFlags(wmem);	1✔
456	setMemoryFlags(wmem, empty ? flags \| EMPTY_BIT_MASK : flags & ~EMPTY_BIT_MASK);	1✔
457	}	1✔
458
459	static void setMemoryLevelZeroSortedFlag(final WritableMemory wmem, final boolean levelZeroSorted) {
460	final int flags = getMemoryFlags(wmem);	1✔
461	setMemoryFlags(wmem, levelZeroSorted ? flags \| LEVEL_ZERO_SORTED_BIT_MASK : flags & ~LEVEL_ZERO_SORTED_BIT_MASK);	1✔
462	}	1✔
463
464	static void setMemoryK(final WritableMemory wmem, final int memK) {
465	wmem.putShort(K_SHORT_ADR, (short) memK);	1✔
466	}	1✔
467
468	static void setMemoryM(final WritableMemory wmem, final int memM) {
469	wmem.putByte(M_BYTE_ADR, (byte) memM);	1✔
470	}	1✔
471
472	static void setMemoryN(final WritableMemory wmem, final long memN) {
473	wmem.putLong(N_LONG_ADR, memN);	1✔
474	}	1✔
475
476	static void setMemoryMinK(final WritableMemory wmem, final int memMinK) {
477	wmem.putShort(MIN_K_SHORT_ADR, (short) memMinK);	1✔
478	}	1✔
479
480	static void setMemoryNumLevels(final WritableMemory wmem, final int memNumLevels) {
481	wmem.putByte(NUM_LEVELS_BYTE_ADR, (byte) memNumLevels);	1✔
482	}	1✔
483
484	}

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