folly/folly/GroupVarint.cpp

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * 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 FOLLY_HAVE_GROUP_VARINT
namespace folly {

const uint32_t GroupVarint32::kMask[] = …;

const uint64_t GroupVarint64::kMask[] = …;

namespace detail {

struct group_varint_table_base_make_item { … };

struct group_varint_table_length_make_item : group_varint_table_base_make_item { … };

//  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 { … };

#if FOLLY_SSE >= 4
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 = …;

} // namespace detail

} // namespace folly
#endif