123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153 |
- /*
- * Copyright 2012-present Facebook, Inc.
- *
- * Licensed 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.
- */
- #include <folly/GroupVarint.h>
- #include <folly/container/Array.h>
- #if HAVE_GROUP_VARINT
- namespace folly {
- const uint32_t GroupVarint32::kMask[] = {
- 0xff,
- 0xffff,
- 0xffffff,
- 0xffffffff,
- };
- const uint64_t GroupVarint64::kMask[] = {
- 0xff,
- 0xffff,
- 0xffffff,
- 0xffffffff,
- 0xffffffffffULL,
- 0xffffffffffffULL,
- 0xffffffffffffffULL,
- 0xffffffffffffffffULL,
- };
- namespace detail {
- struct group_varint_table_base_make_item {
- constexpr std::size_t get_d(std::size_t index, std::size_t j) const {
- return 1u + ((index >> (2 * j)) & 3u);
- }
- constexpr std::size_t get_offset(std::size_t index, std::size_t j) const {
- // clang-format off
- return
- (j > 0 ? get_d(index, 0) : 0) +
- (j > 1 ? get_d(index, 1) : 0) +
- (j > 2 ? get_d(index, 2) : 0) +
- (j > 3 ? get_d(index, 3) : 0) +
- 0;
- // clang-format on
- }
- };
- struct group_varint_table_length_make_item : group_varint_table_base_make_item {
- constexpr std::uint8_t operator()(std::size_t index) const {
- return 1u + get_offset(index, 4);
- }
- };
- // Reference: http://www.stepanovpapers.com/CIKM_2011.pdf
- //
- // From 17 encoded bytes, we may use between 5 and 17 bytes to encode 4
- // integers. The first byte is a key that indicates how many bytes each of
- // the 4 integers takes:
- //
- // bit 0..1: length-1 of first integer
- // bit 2..3: length-1 of second integer
- // bit 4..5: length-1 of third integer
- // bit 6..7: length-1 of fourth integer
- //
- // The value of the first byte is used as the index in a table which returns
- // a mask value for the SSSE3 PSHUFB instruction, which takes an XMM register
- // (16 bytes) and shuffles bytes from it into a destination XMM register
- // (optionally setting some of them to 0)
- //
- // For example, if the key has value 4, that means that the first integer
- // uses 1 byte, the second uses 2 bytes, the third and fourth use 1 byte each,
- // so we set the mask value so that
- //
- // r[0] = a[0]
- // r[1] = 0
- // r[2] = 0
- // r[3] = 0
- //
- // r[4] = a[1]
- // r[5] = a[2]
- // r[6] = 0
- // r[7] = 0
- //
- // r[8] = a[3]
- // r[9] = 0
- // r[10] = 0
- // r[11] = 0
- //
- // r[12] = a[4]
- // r[13] = 0
- // r[14] = 0
- // r[15] = 0
- struct group_varint_table_sse_mask_make_item
- : group_varint_table_base_make_item {
- constexpr auto partial_item(std::size_t d, std::size_t offset, std::size_t k)
- const {
- // if k < d, the j'th integer uses d bytes, consume them
- // set remaining bytes in result to 0
- // 0xff: set corresponding byte in result to 0
- return std::uint32_t((k < d ? offset + k : std::size_t(0xff)) << (8 * k));
- }
- constexpr auto item_impl(std::size_t d, std::size_t offset) const {
- // clang-format off
- return
- partial_item(d, offset, 0) |
- partial_item(d, offset, 1) |
- partial_item(d, offset, 2) |
- partial_item(d, offset, 3) |
- 0;
- // clang-format on
- }
- constexpr auto item(std::size_t index, std::size_t j) const {
- return item_impl(get_d(index, j), get_offset(index, j));
- }
- constexpr auto operator()(std::size_t index) const {
- return std::array<std::uint32_t, 4>{{
- item(index, 0),
- item(index, 1),
- item(index, 2),
- item(index, 3),
- }};
- }
- };
- #if FOLLY_SSE >= 3
- alignas(16) FOLLY_STORAGE_CONSTEXPR
- decltype(groupVarintSSEMasks) groupVarintSSEMasks =
- make_array_with<256>(group_varint_table_sse_mask_make_item{});
- #endif
- FOLLY_STORAGE_CONSTEXPR decltype(groupVarintLengths) groupVarintLengths =
- make_array_with<256>(group_varint_table_length_make_item{});
- } // namespace detail
- } // namespace folly
- #endif
|