|
| 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 | +#include "exec/sink/paimon_native_row_hash.h" |
| 19 | + |
| 20 | +#include <bit> |
| 21 | +#include <cstring> |
| 22 | +#include <limits> |
| 23 | + |
| 24 | +namespace doris::paimon_native { |
| 25 | +namespace { |
| 26 | + |
| 27 | +constexpr uint32_t MURMUR_C1 = 0xcc9e2d51U; |
| 28 | +constexpr uint32_t MURMUR_C2 = 0x1b873593U; |
| 29 | +constexpr uint32_t MURMUR_SEED = 42U; |
| 30 | + |
| 31 | +uint32_t rotate_left(uint32_t value, int distance) { |
| 32 | + return (value << distance) | (value >> (32 - distance)); |
| 33 | +} |
| 34 | + |
| 35 | +uint32_t mix_k1(uint32_t value) { |
| 36 | + value *= MURMUR_C1; |
| 37 | + value = rotate_left(value, 15); |
| 38 | + value *= MURMUR_C2; |
| 39 | + return value; |
| 40 | +} |
| 41 | + |
| 42 | +uint32_t mix_h1(uint32_t hash, uint32_t value) { |
| 43 | + hash ^= value; |
| 44 | + hash = rotate_left(hash, 13); |
| 45 | + return hash * 5U + 0xe6546b64U; |
| 46 | +} |
| 47 | + |
| 48 | +uint32_t fmix(uint32_t hash, size_t length) { |
| 49 | + hash ^= static_cast<uint32_t>(length); |
| 50 | + hash ^= hash >> 16; |
| 51 | + hash *= 0x85ebca6bU; |
| 52 | + hash ^= hash >> 13; |
| 53 | + hash *= 0xc2b2ae35U; |
| 54 | + hash ^= hash >> 16; |
| 55 | + return hash; |
| 56 | +} |
| 57 | + |
| 58 | +template <typename T> |
| 59 | +void put_native(std::vector<uint8_t>* bytes, size_t offset, T value) { |
| 60 | + std::memcpy(bytes->data() + offset, &value, sizeof(value)); |
| 61 | +} |
| 62 | + |
| 63 | +int32_t java_abs_remainder(int32_t value, int32_t divisor) { |
| 64 | + int32_t remainder = value % divisor; |
| 65 | + return remainder < 0 ? -remainder : remainder; |
| 66 | +} |
| 67 | + |
| 68 | +size_t round_to_word(size_t size) { |
| 69 | + return (size + 7U) & ~size_t {7U}; |
| 70 | +} |
| 71 | + |
| 72 | +} // namespace |
| 73 | + |
| 74 | +BinaryRowEncoder::BinaryRowEncoder(size_t arity) |
| 75 | + : _arity(arity), |
| 76 | + _null_bits_size((arity + 63U + 8U) / 64U * 8U), |
| 77 | + _fixed_size(_null_bits_size + arity * 8U), |
| 78 | + _cursor(_fixed_size), |
| 79 | + _bytes(_fixed_size, 0) {} |
| 80 | + |
| 81 | +void BinaryRowEncoder::reset() { |
| 82 | + _cursor = _fixed_size; |
| 83 | + _bytes.assign(_fixed_size, 0); |
| 84 | +} |
| 85 | + |
| 86 | +bool BinaryRowEncoder::_valid_position(size_t position) const { |
| 87 | + return position < _arity; |
| 88 | +} |
| 89 | + |
| 90 | +size_t BinaryRowEncoder::_field_offset(size_t position) const { |
| 91 | + return _null_bits_size + position * 8U; |
| 92 | +} |
| 93 | + |
| 94 | +void BinaryRowEncoder::_set_null_bit(size_t position) { |
| 95 | + const size_t bit_index = position + 8U; |
| 96 | + _bytes[bit_index >> 3U] |= static_cast<uint8_t>(1U << (bit_index & 7U)); |
| 97 | +} |
| 98 | + |
| 99 | +void BinaryRowEncoder::_ensure_capacity(size_t size) { |
| 100 | + if (_bytes.size() < size) { |
| 101 | + _bytes.resize(size, 0); |
| 102 | + } |
| 103 | +} |
| 104 | + |
| 105 | +void BinaryRowEncoder::_set_offset_and_size(size_t position, uint32_t offset, uint32_t size) { |
| 106 | + uint64_t offset_and_size = (static_cast<uint64_t>(offset) << 32U) | size; |
| 107 | + put_native(&_bytes, _field_offset(position), offset_and_size); |
| 108 | +} |
| 109 | + |
| 110 | +bool BinaryRowEncoder::set_null(size_t position) { |
| 111 | + if (!_valid_position(position)) { |
| 112 | + return false; |
| 113 | + } |
| 114 | + _set_null_bit(position); |
| 115 | + std::fill_n(_bytes.begin() + _field_offset(position), 8, uint8_t {0}); |
| 116 | + return true; |
| 117 | +} |
| 118 | + |
| 119 | +bool BinaryRowEncoder::write_boolean(size_t position, bool value) { |
| 120 | + return write_tinyint(position, value ? 1 : 0); |
| 121 | +} |
| 122 | + |
| 123 | +bool BinaryRowEncoder::write_tinyint(size_t position, int8_t value) { |
| 124 | + if (!_valid_position(position)) { |
| 125 | + return false; |
| 126 | + } |
| 127 | + put_native(&_bytes, _field_offset(position), value); |
| 128 | + return true; |
| 129 | +} |
| 130 | + |
| 131 | +bool BinaryRowEncoder::write_smallint(size_t position, int16_t value) { |
| 132 | + if (!_valid_position(position)) { |
| 133 | + return false; |
| 134 | + } |
| 135 | + put_native(&_bytes, _field_offset(position), value); |
| 136 | + return true; |
| 137 | +} |
| 138 | + |
| 139 | +bool BinaryRowEncoder::write_int(size_t position, int32_t value) { |
| 140 | + if (!_valid_position(position)) { |
| 141 | + return false; |
| 142 | + } |
| 143 | + put_native(&_bytes, _field_offset(position), value); |
| 144 | + return true; |
| 145 | +} |
| 146 | + |
| 147 | +bool BinaryRowEncoder::write_bigint(size_t position, int64_t value) { |
| 148 | + if (!_valid_position(position)) { |
| 149 | + return false; |
| 150 | + } |
| 151 | + put_native(&_bytes, _field_offset(position), value); |
| 152 | + return true; |
| 153 | +} |
| 154 | + |
| 155 | +bool BinaryRowEncoder::write_float(size_t position, float value) { |
| 156 | + if (!_valid_position(position)) { |
| 157 | + return false; |
| 158 | + } |
| 159 | + put_native(&_bytes, _field_offset(position), value); |
| 160 | + return true; |
| 161 | +} |
| 162 | + |
| 163 | +bool BinaryRowEncoder::write_double(size_t position, double value) { |
| 164 | + if (!_valid_position(position)) { |
| 165 | + return false; |
| 166 | + } |
| 167 | + put_native(&_bytes, _field_offset(position), value); |
| 168 | + return true; |
| 169 | +} |
| 170 | + |
| 171 | +bool BinaryRowEncoder::_write_bytes(size_t position, std::string_view bytes) { |
| 172 | + if (!_valid_position(position) || bytes.size() > std::numeric_limits<uint32_t>::max()) { |
| 173 | + return false; |
| 174 | + } |
| 175 | + if (bytes.size() <= 7U) { |
| 176 | + uint64_t inline_value = (static_cast<uint64_t>(bytes.size()) | 0x80U) << 56U; |
| 177 | + for (size_t index = 0; index < bytes.size(); ++index) { |
| 178 | + if constexpr (std::endian::native == std::endian::little) { |
| 179 | + inline_value |= static_cast<uint64_t>(static_cast<uint8_t>(bytes[index])) |
| 180 | + << (index * 8U); |
| 181 | + } else { |
| 182 | + inline_value |= static_cast<uint64_t>(static_cast<uint8_t>(bytes[index])) |
| 183 | + << ((6U - index) * 8U); |
| 184 | + } |
| 185 | + } |
| 186 | + put_native(&_bytes, _field_offset(position), inline_value); |
| 187 | + return true; |
| 188 | + } |
| 189 | + |
| 190 | + const size_t rounded_size = round_to_word(bytes.size()); |
| 191 | + if (rounded_size > std::numeric_limits<uint32_t>::max() || |
| 192 | + _cursor > std::numeric_limits<uint32_t>::max() - rounded_size) { |
| 193 | + return false; |
| 194 | + } |
| 195 | + _ensure_capacity(_cursor + rounded_size); |
| 196 | + std::fill_n(_bytes.begin() + _cursor, rounded_size, uint8_t {0}); |
| 197 | + std::memcpy(_bytes.data() + _cursor, bytes.data(), bytes.size()); |
| 198 | + _set_offset_and_size(position, static_cast<uint32_t>(_cursor), |
| 199 | + static_cast<uint32_t>(bytes.size())); |
| 200 | + _cursor += rounded_size; |
| 201 | + return true; |
| 202 | +} |
| 203 | + |
| 204 | +bool BinaryRowEncoder::write_string(size_t position, std::string_view utf8) { |
| 205 | + return _write_bytes(position, utf8); |
| 206 | +} |
| 207 | + |
| 208 | +bool BinaryRowEncoder::write_binary(size_t position, std::string_view bytes) { |
| 209 | + return _write_bytes(position, bytes); |
| 210 | +} |
| 211 | + |
| 212 | +int32_t BinaryRowEncoder::hash() const { |
| 213 | + return binary_row_hash(std::string_view(reinterpret_cast<const char*>(_bytes.data()), _cursor)); |
| 214 | +} |
| 215 | + |
| 216 | +int32_t binary_row_hash(std::string_view bytes) { |
| 217 | + uint32_t hash = MURMUR_SEED; |
| 218 | + size_t offset = 0; |
| 219 | + const size_t aligned_length = bytes.size() - bytes.size() % 4U; |
| 220 | + for (; offset < aligned_length; offset += 4U) { |
| 221 | + uint32_t word; |
| 222 | + std::memcpy(&word, bytes.data() + offset, sizeof(word)); |
| 223 | + hash = mix_h1(hash, mix_k1(word)); |
| 224 | + } |
| 225 | + // This is intentionally Paimon's per-byte tail loop, not the standard |
| 226 | + // Murmur3 packed tail. BinaryRows are word-aligned, but keeping this exact |
| 227 | + // makes the primitive independently testable. |
| 228 | + for (; offset < bytes.size(); ++offset) { |
| 229 | + int32_t signed_byte = static_cast<int8_t>(bytes[offset]); |
| 230 | + hash = mix_h1(hash, mix_k1(static_cast<uint32_t>(signed_byte))); |
| 231 | + } |
| 232 | + uint32_t mixed = fmix(hash, bytes.size()); |
| 233 | + int32_t result; |
| 234 | + std::memcpy(&result, &mixed, sizeof(result)); |
| 235 | + return result; |
| 236 | +} |
| 237 | + |
| 238 | +std::optional<uint32_t> default_bucket(int32_t bucket_key_hash, int32_t num_buckets) { |
| 239 | + if (num_buckets <= 0) { |
| 240 | + return std::nullopt; |
| 241 | + } |
| 242 | + return static_cast<uint32_t>(java_abs_remainder(bucket_key_hash, num_buckets)); |
| 243 | +} |
| 244 | + |
| 245 | +} // namespace doris::paimon_native |
0 commit comments