|
| 1 | +# Licensed to the Apache Software Foundation (ASF) under one |
| 2 | +# or more contributor license agreements. See the NOTICE file |
| 3 | +# distributed with this work for additional information |
| 4 | +# regarding copyright ownership. The ASF licenses this file |
| 5 | +# to you under the Apache License, Version 2.0 (the |
| 6 | +# "License"); you may not use this file except in compliance |
| 7 | +# with the License. You may obtain a copy of the License at |
| 8 | +# |
| 9 | +# http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | +# |
| 11 | +# Unless required by applicable law or agreed to in writing, |
| 12 | +# software distributed under the License is distributed on an |
| 13 | +# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 14 | +# KIND, either express or implied. See the License for the |
| 15 | +# specific language governing permissions and limitations |
| 16 | +# under the License. |
| 17 | + |
| 18 | +"""A transcription of Arrow C++'s parquet/chunker_internal.cc, used as an oracle. |
| 19 | +
|
| 20 | +Written from the C++ source rather than from the Java port, and the gear tables are |
| 21 | +regenerated from their MD5 specification rather than copied, so agreement between this and |
| 22 | +ContentDefinedChunker is evidence the port is faithful. `reference.py` is the other half of |
| 23 | +the picture: it drives the real Arrow C++ through pyarrow, which is stronger but needs |
| 24 | +pyarrow installed. This needs nothing but the standard library. |
| 25 | +
|
| 26 | + python3 dev/cdc/model.py vectors # the expected chunk sizes the Java tests assert |
| 27 | +
|
| 28 | +Every case under `vectors` names the test method it feeds, and the two must be kept in step. |
| 29 | +""" |
| 30 | +import hashlib |
| 31 | +import struct |
| 32 | +import sys |
| 33 | + |
| 34 | +NUM_GEARHASH_TABLES = 8 |
| 35 | +MASK64 = (1 << 64) - 1 |
| 36 | + |
| 37 | + |
| 38 | +def gearhash_tables(): |
| 39 | + """chunker_internal_generated.h, from the specification it was generated by.""" |
| 40 | + return [ |
| 41 | + [ |
| 42 | + int(hashlib.md5(bytes([seed] * 64 + [n] * 64)).hexdigest()[:16], 16) |
| 43 | + for n in range(256) |
| 44 | + ] |
| 45 | + for seed in range(NUM_GEARHASH_TABLES) |
| 46 | + ] |
| 47 | + |
| 48 | + |
| 49 | +TABLE = gearhash_tables() |
| 50 | + |
| 51 | + |
| 52 | +def calculate_mask(min_chunk_size, max_chunk_size, norm_level): |
| 53 | + """CalculateMask(), chunker_internal.cc. |
| 54 | +
|
| 55 | + The sum below overflows int64 for envelopes near its maximum, as it does in C++ and in |
| 56 | + arrow-rs; RollingHashMask.calculate rejects those instead. Nothing in the vectors here |
| 57 | + comes near it. |
| 58 | + """ |
| 59 | + if min_chunk_size < 0: |
| 60 | + raise ValueError("min_chunk_size must be non-negative") |
| 61 | + if max_chunk_size <= min_chunk_size: |
| 62 | + raise ValueError("max_chunk_size must be greater than min_chunk_size") |
| 63 | + avg_chunk_size = (min_chunk_size + max_chunk_size) // 2 |
| 64 | + target_size = (avg_chunk_size - min_chunk_size) // NUM_GEARHASH_TABLES |
| 65 | + target_bits = target_size.bit_length() |
| 66 | + mask_bits = 0 if target_bits == 0 else target_bits - 1 |
| 67 | + effective_bits = mask_bits - norm_level |
| 68 | + if effective_bits < 1 or effective_bits > 63: |
| 69 | + raise ValueError( |
| 70 | + "The number of bits in the CDC mask must be between 1 and 63, got %d" % effective_bits |
| 71 | + ) |
| 72 | + return (MASK64 << (64 - effective_bits)) & MASK64 |
| 73 | + |
| 74 | + |
| 75 | +class Chunker: |
| 76 | + """ContentDefinedChunker::Impl, chunker_internal.cc.""" |
| 77 | + |
| 78 | + def __init__(self, min_chunk_size, max_chunk_size, norm_level, max_def=0, max_rep=0): |
| 79 | + self.min_chunk_size = min_chunk_size |
| 80 | + self.max_chunk_size = max_chunk_size |
| 81 | + self.mask = calculate_mask(min_chunk_size, max_chunk_size, norm_level) |
| 82 | + self.max_def = max_def |
| 83 | + self.max_rep = max_rep |
| 84 | + self.rolling_hash = 0 |
| 85 | + self.has_matched = False |
| 86 | + self.nth_run = 0 |
| 87 | + self.chunk_size = 0 |
| 88 | + |
| 89 | + def roll(self, data): |
| 90 | + """Roll(), for a value already reduced to its storage bytes.""" |
| 91 | + self.chunk_size += len(data) |
| 92 | + if self.chunk_size < self.min_chunk_size: |
| 93 | + return |
| 94 | + for byte in data: |
| 95 | + self.rolling_hash = ((self.rolling_hash << 1) + TABLE[self.nth_run][byte]) & MASK64 |
| 96 | + self.has_matched = self.has_matched or (self.rolling_hash & self.mask) == 0 |
| 97 | + |
| 98 | + def need_new_chunk(self): |
| 99 | + """NeedNewChunk(). Note what is not reset: the rolling hash, ever, and nth_run on |
| 100 | + the hard size cut.""" |
| 101 | + if self.has_matched: |
| 102 | + self.has_matched = False |
| 103 | + self.nth_run += 1 |
| 104 | + if self.nth_run >= NUM_GEARHASH_TABLES: |
| 105 | + self.nth_run = 0 |
| 106 | + self.chunk_size = 0 |
| 107 | + return True |
| 108 | + if self.chunk_size >= self.max_chunk_size: |
| 109 | + self.chunk_size = 0 |
| 110 | + return True |
| 111 | + return False |
| 112 | + |
| 113 | + def offer(self, value=None, rep=0, definition=0): |
| 114 | + """One triplet, in the order Calculate() rolls them: definition, repetition, value. |
| 115 | +
|
| 116 | + Returns whether a page ends immediately before it. The caller counts values, the way |
| 117 | + ChunkingColumnWriter does, rather than slicing a materialised column as C++ does. |
| 118 | + """ |
| 119 | + if self.max_def > 0: |
| 120 | + self.roll(struct.pack("<h", definition)) |
| 121 | + if self.max_rep > 0: |
| 122 | + self.roll(struct.pack("<h", rep)) |
| 123 | + if definition == self.max_def and value is not None: |
| 124 | + self.roll(value) |
| 125 | + if self.max_rep and rep != 0: |
| 126 | + # C++ only calls NeedNewChunk() at a record start, so a match found mid-record |
| 127 | + # carries forward instead of being consumed here. |
| 128 | + return False |
| 129 | + return self.need_new_chunk() |
| 130 | + |
| 131 | + |
| 132 | +def chunk_sizes(chunker, values): |
| 133 | + """Value counts per page, counted as TestContentDefinedChunker counts them.""" |
| 134 | + sizes = [] |
| 135 | + current = 0 |
| 136 | + for value in values: |
| 137 | + if chunker.offer(value) and current > 0: |
| 138 | + sizes.append(current) |
| 139 | + current = 0 |
| 140 | + current += 1 |
| 141 | + if current > 0: |
| 142 | + sizes.append(current) |
| 143 | + return sizes |
| 144 | + |
| 145 | + |
| 146 | +def lcg(count): |
| 147 | + """The value stream the Java tests generate, as unsigned 64-bit.""" |
| 148 | + x = 0x243F6A8885A308D3 |
| 149 | + out = [] |
| 150 | + for _ in range(count): |
| 151 | + x = (6364136223846793005 * x + 1442695040888963407) & MASK64 |
| 152 | + out.append(x) |
| 153 | + return out |
| 154 | + |
| 155 | + |
| 156 | +def vectors(): |
| 157 | + """The chunk size vectors TestContentDefinedChunker asserts, by test method name. |
| 158 | +
|
| 159 | + Each case reproduces its Java counterpart's value stream. All of them drive a flat |
| 160 | + required column through a 0/64-byte envelope, where a chunk of 8 eight-byte values is a |
| 161 | + maximum-size cut and anything shorter is the rolling hash completing a run. |
| 162 | + """ |
| 163 | + def scaled(count): |
| 164 | + """chunksIntegers: i * 0x9E3779B1 in 32-bit two's complement.""" |
| 165 | + return [struct.pack("<I", (i * 0x9E3779B1) & 0xFFFFFFFF) for i in range(count)] |
| 166 | + |
| 167 | + def lcg_from(seed, count): |
| 168 | + x = seed |
| 169 | + out = [] |
| 170 | + for _ in range(count): |
| 171 | + x = (6364136223846793005 * x + 1442695040888963407) & MASK64 |
| 172 | + out.append(x) |
| 173 | + return out |
| 174 | + |
| 175 | + # The chunker hashes a value's storage bytes, little-endian: INT64 and DOUBLE are the low |
| 176 | + # eight bytes of the stream, INT32 and FLOAT the low four. |
| 177 | + cases = [ |
| 178 | + ("interleavesHashAndMaximumSizeCuts", |
| 179 | + [struct.pack("<Q", v) for v in lcg(120)]), |
| 180 | + ("chunksIntegers", scaled(120)), |
| 181 | + ("chunksDoubles", |
| 182 | + [struct.pack("<Q", v) for v in lcg_from(99, 120)]), |
| 183 | + # Quiet NaN payloads: intBitsToFloat/longBitsToDouble may quiet a signalling pattern, |
| 184 | + # and which patterns signal is platform dependent, so a signalling range would make |
| 185 | + # these vectors architecture dependent. |
| 186 | + ("floatsHashTheirRawBitsIncludingNanPayloads", |
| 187 | + [struct.pack("<I", 0x7FC00001 + i) for i in range(120)]), |
| 188 | + ("doublesHashTheirRawBitsIncludingNanPayloads", |
| 189 | + [struct.pack("<Q", 0x7FF8000000000001 + i) for i in range(120)]), |
| 190 | + ] |
| 191 | + |
| 192 | + for name, values in cases: |
| 193 | + sizes = chunk_sizes(Chunker(0, 64, 0), values) |
| 194 | + print("%-46s %s" % (name, ", ".join(str(s) for s in sizes))) |
| 195 | + |
| 196 | + |
| 197 | +if __name__ == "__main__": |
| 198 | + if len(sys.argv) > 1 and sys.argv[1] == "vectors": |
| 199 | + vectors() |
| 200 | + else: |
| 201 | + print(__doc__) |
| 202 | + sys.exit(2) |
0 commit comments