orc-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rip-nsk <...@git.apache.org>
Subject [GitHub] orc pull request #273: ORC-343 Enable C++ writer to support RleV2
Date Fri, 25 May 2018 15:01:59 GMT
Github user rip-nsk commented on a diff in the pull request:

    https://github.com/apache/orc/pull/273#discussion_r190919609
  
    --- Diff: c++/src/RleEncoderV2.cc ---
    @@ -0,0 +1,768 @@
    +/**
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with option work for additional information
    + * regarding copyright ownership.  The ASF licenses option file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use option 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 "Adaptor.hh"
    +#include "Compression.hh"
    +#include "RLEv2.hh"
    +#include "RLEV2Util.hh"
    +
    +#define MAX_LITERAL_SIZE 512
    +#define MAX_SHORT_REPEAT_LENGTH 10
    +
    +namespace orc {
    +
    +/**
    + * Compute the bits required to represent pth percentile value
    + * @param data - array
    + * @param p - percentile value (&gt;=0.0 to &lt;=1.0)
    + * @return pth percentile bits
    + */
    +uint32_t RleEncoderV2::percentileBits(int64_t* data, size_t offset, size_t length, double
p, bool reuseHist) {
    +    if ((p > 1.0) || (p <= 0.0)) {
    +        throw InvalidArgument("Invalid p value: " + std::to_string(p));
    +    }
    +
    +    if (!reuseHist) {
    +        // histogram that store the encoded bit requirement for each values.
    +        // maximum number of bits that can encoded is 32 (refer FixedBitSizes)
    +        memset(histgram, 0, 32 * sizeof(int32_t));
    +        // compute the histogram
    +        for(size_t i = offset; i < (offset + length); i++) {
    +            uint32_t idx = encodeBitWidth(findClosestNumBits(data[i]));
    +            histgram[idx] += 1;
    +        }
    +    }
    +
    +    int32_t perLen = static_cast<int32_t>(static_cast<double>(length) * (1.0
- p));
    +
    +    // return the bits required by pth percentile length
    +    for(int32_t i = HIST_LEN - 1; i >= 0; i--) {
    +        perLen -= histgram[i];
    +        if (perLen < 0) {
    +            return decodeBitWidth(static_cast<uint32_t>(i));
    +        }
    +    }
    +
    +    return 0;
    +}
    +
    +RleEncoderV2::RleEncoderV2(std::unique_ptr<BufferedOutputStream> outStream,
    +                           bool hasSigned, bool alignBitPacking) :
    +        RleEncoder(std::move(outStream), hasSigned),
    +        alignedBitPacking(alignBitPacking),
    +        prevDelta(0){
    +    literals = new int64_t[MAX_LITERAL_SIZE];
    +    gapVsPatchList = new int64_t[MAX_LITERAL_SIZE];
    +    zigzagLiterals = new int64_t[MAX_LITERAL_SIZE];
    +    baseRedLiterals = new int64_t[MAX_LITERAL_SIZE];
    +    adjDeltas = new int64_t[MAX_LITERAL_SIZE];
    +}
    +
    +void RleEncoderV2::write(int64_t val) {
    +    if(numLiterals == 0) {
    +        initializeLiterals(val);
    +        return;
    +    }
    +
    +    if(numLiterals == 1) {
    +        prevDelta = val - literals[0];
    +        literals[numLiterals++] = val;
    +
    +        if(val == literals[0]) {
    +            fixedRunLength = 2;
    +            variableRunLength = 0;
    +        } else {
    +            fixedRunLength = 0;
    +            variableRunLength = 2;
    +        }
    +        return;
    +    }
    +
    +    int64_t currentDelta = val - literals[numLiterals - 1];
    +    EncodingOption option = {};
    +    if (prevDelta == 0 && currentDelta == 0) {
    +        // case 1: fixed delta run
    +        literals[numLiterals++] = val;
    +
    +        if (variableRunLength > 0) {
    +            // if variable run is non-zero then we are seeing repeating
    +            // values at the end of variable run in which case fixed Run
    +            // length is 2
    +            fixedRunLength = 2;
    +        }
    +        fixedRunLength++;
    +
    +        // if fixed run met the minimum condition and if variable
    +        // run is non-zero then flush the variable run and shift the
    +        // tail fixed runs to start of the buffer
    +        if (fixedRunLength >= MIN_REPEAT && variableRunLength > 0) {
    +            numLiterals -= MIN_REPEAT;
    +            variableRunLength -= (MIN_REPEAT - 1);
    +
    +            int64_t tailVals[MIN_REPEAT] = {0};
    +
    +            memcpy(tailVals, literals + numLiterals, sizeof(int64_t) * MIN_REPEAT);
    +            determineEncoding(option);
    +            writeValues(option);
    +
    +            // shift tail fixed runs to beginning of the buffer
    +            for (size_t i = 0; i < MIN_REPEAT; ++i) {
    +                literals[numLiterals++] = tailVals[i];
    +            }
    +        }
    +
    +        if (fixedRunLength == MAX_LITERAL_SIZE) {;
    +            determineEncoding(option);
    +            writeValues(option);
    +        }
    +        return;
    +    }
    +
    +    // case 2: variable delta run
    +
    +    // if fixed run length is non-zero and if it satisfies the
    +    // short repeat conditions then write the values as short repeats
    +    // else use delta encoding
    +    if (fixedRunLength >= MIN_REPEAT) {
    +        if (fixedRunLength <= MAX_SHORT_REPEAT_LENGTH) {
    +            option.encoding = SHORT_REPEAT;
    +        } else {
    +            option.encoding = DELTA;
    +            option.isFixedDelta = true;
    +        }
    +        writeValues(option);
    +    }
    +
    +    // if fixed run length is <MIN_REPEAT and current value is
    +    // different from previous then treat it as variable run
    +    if (fixedRunLength > 0 && fixedRunLength < MIN_REPEAT && val
!= literals[numLiterals - 1]) {
    +        variableRunLength = fixedRunLength;
    +        fixedRunLength = 0;
    +    }
    +
    +    // after writing values re-initialize the variables
    +    if (numLiterals == 0) {
    +        initializeLiterals(val);
    +    } else {
    +        prevDelta = val - literals[numLiterals - 1];
    +        literals[numLiterals++] = val;
    +        variableRunLength++;
    +
    +        if (variableRunLength == MAX_LITERAL_SIZE) {
    +            determineEncoding(option);
    +            writeValues(option);
    +        }
    +    }
    +}
    +
    +void RleEncoderV2::computeZigZagLiterals(EncodingOption &option) {
    +    int64_t zzEncVal = 0;
    +    for (size_t i = 0; i < numLiterals; i++) {
    +        if (isSigned) {
    +            zzEncVal = zigZag(literals[i]);
    +        } else {
    +            zzEncVal = literals[i];
    +        }
    +        zigzagLiterals[option.zigzagLiteralsCount++] = zzEncVal;
    +    }
    +}
    +
    +void RleEncoderV2::preparePatchedBlob(EncodingOption& option) {
    +    // mask will be max value beyond which patch will be generated
    +    int64_t mask = static_cast<int64_t>(1LU << option.brBits95p) - 1;
    +
    +    // since we are considering only 95 percentile, the size of gap and
    +    // patch array can contain only be 5% values
    +    option.patchLength = static_cast<uint32_t>(std::ceil((numLiterals / 20)));
    +
    +    // #bit for patch
    +    option.patchWidth = option.brBits100p - option.brBits95p;
    +    option.patchWidth = getClosestFixedBits(option.patchWidth);
    +
    +    // if patch bit requirement is 64 then it will not possible to pack
    +    // gap and patch together in a long. To make sure gap and patch can be
    +    // packed together adjust the patch width
    +    if (option.patchWidth == 64) {
    +        option.patchWidth = 56;
    +        option.brBits95p = 8;
    +        mask = static_cast<int64_t>(1LU << option.brBits95p) - 1;
    +    }
    +
    +    uint32_t gapIdx = 0;
    +    uint32_t patchIdx = 0;
    +    size_t prev = 0;
    +    size_t maxGap = 0;
    +
    +    std::vector<int64_t> gapList;
    +    std::vector<int64_t> patchList;
    +
    +    for(size_t i = 0; i < numLiterals; i++) {
    +        // if value is above mask then create the patch and record the gap
    +        if (baseRedLiterals[i] > mask) {
    +            size_t gap = i - prev;
    +            if (gap > maxGap) {
    +                maxGap = gap;
    +            }
    +
    +            // gaps are relative, so store the previous patched value index
    +            prev = i;
    +            gapList.push_back(static_cast<int64_t>(gap));
    +            gapIdx++;
    +
    +            // extract the most significant bits that are over mask bits
    +            int64_t patch = baseRedLiterals[i] >> option.brBits95p;
    +            patchList.push_back(patch);
    +            patchIdx++;
    +
    +            // strip off the MSB to enable safe bit packing
    +            baseRedLiterals[i] &= mask;
    +        }
    +    }
    +
    +    // adjust the patch length to number of entries in gap list
    +    option.patchLength = gapIdx;
    +
    +    // if the element to be patched is the first and only element then
    +    // max gap will be 0, but to store the gap as 0 we need atleast 1 bit
    +    if (maxGap == 0 && option.patchLength != 0) {
    +        option.patchGapWidth = 1;
    +    } else {
    +        option.patchGapWidth = findClosestNumBits(static_cast<int64_t>(maxGap));
    +    }
    +
    +    // special case: if the patch gap width is greater than 256, then
    +    // we need 9 bits to encode the gap width. But we only have 3 bits in
    +    // header to record the gap width. To deal with this case, we will save
    +    // two entries in patch list in the following way
    +    // 256 gap width => 0 for patch value
    +    // actual gap - 256 => actual patch value
    +    // We will do the same for gap width = 511. If the element to be patched is
    +    // the last element in the scope then gap width will be 511. In this case we
    +    // will have 3 entries in the patch list in the following way
    +    // 255 gap width => 0 for patch value
    +    // 255 gap width => 0 for patch value
    +    // 1 gap width => actual patch value
    +    if (option.patchGapWidth > 8) {
    +        option.patchGapWidth = 8;
    +        // for gap = 511, we need two additional entries in patch list
    +        if (maxGap == 511) {
    +            option.patchLength += 2;
    +        } else {
    +            option.patchLength += 1;
    +        }
    +    }
    +
    +    // create gap vs patch list
    +    gapIdx = 0;
    +    patchIdx = 0;
    +    for(size_t i = 0; i < option.patchLength; i++) {
    +        int64_t g = gapList[gapIdx++];
    +        int64_t p = patchList[patchIdx++];
    +        while (g > 255) {
    +            gapVsPatchList[option.gapVsPatchListCount++] = (255L << option.patchWidth);
    +            i++;
    +            g -= 255;
    +        }
    +
    +        // store patch value in LSBs and gap in MSBs
    +        gapVsPatchList[option.gapVsPatchListCount++] = ((g << option.patchWidth)
| p);
    +    }
    +}
    +
    +void RleEncoderV2::determineEncoding(EncodingOption& option) {
    +    // we need to compute zigzag values for DIRECT encoding if we decide to
    +    // break early for delta overflows or for shorter runs
    +    computeZigZagLiterals(option);
    +
    +    option.zzBits100p = percentileBits(zigzagLiterals, 0, numLiterals, 1.0);
    +
    +    // not a big win for shorter runs to determine encoding
    +    if (numLiterals <= MIN_REPEAT) {
    +        option.encoding = DIRECT;
    +        return;
    +    }
    +
    +    // DELTA encoding check
    +
    +    // for identifying monotonic sequences
    +    bool isIncreasing = true;
    +    bool isDecreasing = true;
    +    option.isFixedDelta = true;
    +
    +    option.min = literals[0];
    +    int64_t max = literals[0];
    +    int64_t initialDelta = literals[1] - literals[0];
    +    int64_t currDelta = 0;
    +    int64_t deltaMax = 0;
    +    adjDeltas[option.adjDeltasCount++] = initialDelta;
    +
    +    for (size_t i = 1; i < numLiterals; i++) {
    +        const int64_t l1 = literals[i];
    +        const int64_t l0 = literals[i - 1];
    +        currDelta = l1 - l0;
    +        option.min = std::min(option.min, l1);
    +        max = std::max(max, l1);
    +
    +        isIncreasing &= (l0 <= l1);
    +        isDecreasing &= (l0 >= l1);
    +
    +        option.isFixedDelta &= (currDelta == initialDelta);
    +        if (i > 1) {
    +            adjDeltas[option.adjDeltasCount++] = std::abs(currDelta);
    +            deltaMax = std::max(deltaMax, adjDeltas[i - 1]);
    +        }
    +    }
    +
    +    // it's faster to exit under delta overflow condition without checking for
    +    // PATCHED_BASE condition as encoding using DIRECT is faster and has less
    +    // overhead than PATCHED_BASE
    +    if (!isSafeSubtract(max, option.min)) {
    +        option.encoding = DIRECT;
    +        return;
    +    }
    +
    +    // invariant - subtracting any number from any other in the literals after
    +    // option point won't overflow
    +
    +    // if min is equal to max then the delta is 0, option condition happens for
    +    // fixed values run >10 which cannot be encoded with SHORT_REPEAT
    +    if (option.min == max) {
    +        if (!option.isFixedDelta) {
    +            throw InvalidArgument(std::to_string(option.min) + "==" + std::to_string(max)
+ ", isFixedDelta cannot be false");
    +        }
    +
    +        if(currDelta != 0) {
    +            throw InvalidArgument(std::to_string(option.min) + "==" + std::to_string(max)
+ ", currDelta should be zero");
    +        }
    +        option.fixedDelta = 0;
    +        option.encoding = DELTA;
    +        return;
    +    }
    +
    +    if (option.isFixedDelta) {
    +        if (currDelta != initialDelta) {
    +            throw InvalidArgument("currDelta should be equal to initialDelta for fixed
delta encoding");
    +        }
    +
    +        option.encoding = DELTA;
    +        option.fixedDelta = currDelta;
    +        return;
    +    }
    +
    +    // if initialDelta is 0 then we cannot delta encode as we cannot identify
    +    // the sign of deltas (increasing or decreasing)
    +    if (initialDelta != 0) {
    +        // stores the number of bits required for packing delta blob in
    +        // delta encoding
    +        option.bitsDeltaMax = findClosestNumBits(deltaMax);
    +
    +        // monotonic condition
    +        if (isIncreasing || isDecreasing) {
    +            option.encoding = DELTA;
    +            return;
    +        }
    +    }
    +
    +    // PATCHED_BASE encoding check
    +
    +    // percentile values are computed for the zigzag encoded values. if the
    +    // number of bit requirement between 90th and 100th percentile varies
    +    // beyond a threshold then we need to patch the values. if the variation
    +    // is not significant then we can use direct encoding
    +
    +    option.zzBits90p = percentileBits(zigzagLiterals, 0, numLiterals, 0.9, true);
    +    uint32_t diffBitsLH = option.zzBits100p - option.zzBits90p;
    +
    +    // if the difference between 90th percentile and 100th percentile fixed
    +    // bits is > 1 then we need patch the values
    +    if (diffBitsLH > 1) {
    +
    +        // patching is done only on base reduced values.
    +        // remove base from literals
    +        for (size_t i = 0; i < numLiterals; i++) {
    +            baseRedLiterals[option.baseRedLiteralsCount++] = (literals[i] - option.min);
    +        }
    +
    +        // 95th percentile width is used to determine max allowed value
    +        // after which patching will be done
    +        option.brBits95p = percentileBits(baseRedLiterals, 0, numLiterals, 0.95);
    +
    +        // 100th percentile is used to compute the max patch width
    +        option.brBits100p = percentileBits(baseRedLiterals, 0, numLiterals, 1.0, true);
    +
    +        // after base reducing the values, if the difference in bits between
    +        // 95th percentile and 100th percentile value is zero then there
    +        // is no point in patching the values, in which case we will
    +        // fallback to DIRECT encoding.
    +        // The decision to use patched base was based on zigzag values, but the
    +        // actual patching is done on base reduced literals.
    +        if ((option.brBits100p - option.brBits95p) != 0) {
    +            option.encoding = PATCHED_BASE;
    +            preparePatchedBlob(option);
    +            return;
    +        } else {
    +            option.encoding = DIRECT;
    +            return;
    +        }
    +    } else {
    +        // if difference in bits between 95th percentile and 100th percentile is
    +        // 0, then patch length will become 0. Hence we will fallback to direct
    +        option.encoding = DIRECT;
    +        return;
    +    }
    +}
    +
    +uint64_t RleEncoderV2::flush() {
    +    if (numLiterals != 0) {
    +        EncodingOption option = {};
    +        if (variableRunLength != 0) {
    +            determineEncoding(option);
    +            writeValues(option);
    +        } else if (fixedRunLength != 0) {
    +            if (fixedRunLength < MIN_REPEAT) {
    +                variableRunLength = fixedRunLength;
    +                fixedRunLength = 0;
    +                determineEncoding(option);
    +                writeValues(option);
    +            } else if (fixedRunLength >= MIN_REPEAT
    +                       && fixedRunLength <= MAX_SHORT_REPEAT_LENGTH) {
    +                option.encoding = SHORT_REPEAT;
    +                writeValues(option);
    +            } else {
    +                option.encoding = DELTA;
    +                option.isFixedDelta = true;
    +                writeValues(option);
    +            }
    +        }
    +    }
    +
    +    outputStream->BackUp(static_cast<int>(bufferLength - bufferPosition));
    +    uint64_t dataSize = outputStream->flush();
    +    bufferLength = bufferPosition = 0;
    +    return dataSize;
    +}
    +
    +void RleEncoderV2::writeValues(EncodingOption& option) {
    +    if (numLiterals != 0) {
    +        switch (option.encoding) {
    +            case SHORT_REPEAT:
    +                writeShortRepeatValues(option);
    +                break;
    +            case DIRECT:
    +                writeDirectValues(option);
    +                break;
    +            case PATCHED_BASE:
    +                writePatchedBasedValues(option);
    +                break;
    +            case DELTA:
    +                writeDeltaValues(option);
    +                break;
    +            default:
    +                throw NotImplementedYet("Not implemented yet");
    +        }
    +
    +        numLiterals = 0;
    +        prevDelta = 0;
    +    }
    +}
    +
    +void RleEncoderV2::writeShortRepeatValues(EncodingOption&) {
    +    int64_t repeatVal;
    +    if (isSigned) {
    +        repeatVal = zigZag(literals[0]);
    +    } else {
    +        repeatVal = literals[0];
    +    }
    +
    +    const uint32_t numBitsRepeatVal = findClosestNumBits(repeatVal);
    +    const uint32_t numBytesRepeatVal = numBitsRepeatVal % 8 == 0 ? (numBitsRepeatVal
>> 3) : ((numBitsRepeatVal >> 3) + 1);
    +
    +    uint32_t header = getOpCode(SHORT_REPEAT);
    +
    +    fixedRunLength -= MIN_REPEAT;
    +    header |= fixedRunLength;
    +    header |= ((numBytesRepeatVal - 1) << 3);
    +
    +    writeByte(static_cast<char>(header));
    +
    +    for(int32_t i = static_cast<int32_t>(numBytesRepeatVal - 1); i >= 0; i--)
{
    +        int64_t b = ((repeatVal >> (i * 8)) & 0xff);
    +        writeByte(static_cast<char>(b));
    +    }
    +
    +    fixedRunLength = 0;
    +}
    +
    +void RleEncoderV2::writeDirectValues(EncodingOption& option) {
    +    // write the number of fixed bits required in next 5 bits
    +    uint32_t fb = option.zzBits100p;
    +    if (alignedBitPacking) {
    +        fb = getClosestAlignedFixedBits(fb);
    +    }
    +
    +    const uint32_t efb = encodeBitWidth(fb) << 1;
    +
    +    // adjust variable run length
    +    variableRunLength -= 1;
    +
    +    // extract the 9th bit of run length
    +    const uint32_t tailBits = (variableRunLength & 0x100) >> 8;
    +
    +    // create first byte of the header
    +    const char headerFirstByte = static_cast<char>(getOpCode(DIRECT) | efb | tailBits);
    +
    +    // second byte of the header stores the remaining 8 bits of runlength
    +    const char headerSecondByte = static_cast<char>(variableRunLength & 0xff);
    +
    +    // write header
    +    writeByte(headerFirstByte);
    +    writeByte(headerSecondByte);
    +
    +    // bit packing the zigzag encoded literals
    +    writeInts(zigzagLiterals, 0, numLiterals, fb);
    +
    +    // reset run length
    +    variableRunLength = 0;
    +}
    +
    +void RleEncoderV2::writePatchedBasedValues(EncodingOption& option) {
    +    // NOTE: Aligned bit packing cannot be applied for PATCHED_BASE encoding
    +    // because patch is applied to MSB bits. For example: If fixed bit width of
    +    // base value is 7 bits and if patch is 3 bits, the actual value is
    +    // constructed by shifting the patch to left by 7 positions.
    +    // actual_value = patch << 7 | base_value
    +    // So, if we align base_value then actual_value can not be reconstructed.
    +
    +    // write the number of fixed bits required in next 5 bits
    +    const uint32_t efb = encodeBitWidth(option.brBits95p) << 1;
    +
    +    // adjust variable run length, they are one off
    +    variableRunLength -= 1;
    +
    +    // extract the 9th bit of run length
    +    const uint32_t tailBits = (variableRunLength & 0x100) >> 8;
    +
    +    // create first byte of the header
    +    const char headerFirstByte = static_cast<char>(getOpCode(PATCHED_BASE) | efb
| tailBits);
    +
    +    // second byte of the header stores the remaining 8 bits of runlength
    +    const char headerSecondByte = static_cast<char>(variableRunLength & 0xff);
    +
    +    // if the min value is negative toggle the sign
    +    const bool isNegative = (option.min < 0);
    +    if (isNegative) {
    +        option.min = -option.min;
    +    }
    +
    +    // find the number of bytes required for base and shift it by 5 bits
    +    // to accommodate patch width. The additional bit is used to store the sign
    +    // of the base value.
    +    const uint32_t baseWidth = findClosestNumBits(option.min) + 1;
    +    const uint32_t baseBytes = baseWidth % 8 == 0 ? baseWidth / 8 : (baseWidth / 8) +
1;
    +    const uint32_t bb = (baseBytes - 1) << 5;
    +
    +    // if the base value is negative then set MSB to 1
    +    if (isNegative) {
    +        option.min |= (1LL << ((baseBytes * 8) - 1));
    +    }
    +
    +    // third byte contains 3 bits for number of bytes occupied by base
    +    // and 5 bits for patchWidth
    +    const char headerThirdByte = static_cast<char>(bb | encodeBitWidth(option.patchWidth));
    +
    +    // fourth byte contains 3 bits for page gap width and 5 bits for
    +    // patch length
    +    const char headerFourthByte = static_cast<char>((option.patchGapWidth - 1)
<< 5 | option.patchLength);
    +
    +    // write header
    +    writeByte(headerFirstByte);
    +    writeByte(headerSecondByte);
    +    writeByte(headerThirdByte);
    +    writeByte(headerFourthByte);
    +
    +    // write the base value using fixed bytes in big endian order
    +    for(int32_t i = static_cast<int32_t>(baseBytes - 1); i >= 0; i--) {
    +        char b = static_cast<char>(((option.min >> (i * 8)) & 0xff));
    +        writeByte(b);
    +    }
    +
    +    // base reduced literals are bit packed
    +    uint32_t closestFixedBits = getClosestFixedBits(option.brBits95p);
    +
    +    writeInts(baseRedLiterals, 0, numLiterals, closestFixedBits);
    +
    +    // write patch list
    +    closestFixedBits = getClosestFixedBits(option.patchGapWidth + option.patchWidth);
    +
    +    writeInts(gapVsPatchList, 0, option.patchLength, closestFixedBits);
    +
    +    // reset run length
    +    variableRunLength = 0;
    +}
    +
    +void RleEncoderV2::writeDeltaValues(EncodingOption& option) {
    +    uint32_t len = 0;
    +    uint32_t fb = option.bitsDeltaMax;
    +    uint32_t efb = 0;
    +
    +    if (alignedBitPacking) {
    +        fb = getClosestAlignedFixedBits(fb);
    +    }
    +
    +    if (option.isFixedDelta) {
    +        // if fixed run length is greater than threshold then it will be fixed
    +        // delta sequence with delta value 0 else fixed delta sequence with
    +        // non-zero delta value
    +        if (fixedRunLength > MIN_REPEAT) {
    +            // ex. sequence: 2 2 2 2 2 2 2 2
    +            len = fixedRunLength - 1;
    +            fixedRunLength = 0;
    +        } else {
    +            // ex. sequence: 4 6 8 10 12 14 16
    +            len = variableRunLength - 1;
    +            variableRunLength = 0;
    +        }
    +    } else {
    +        // fixed width 0 is used for long repeating values.
    +        // sequences that require only 1 bit to encode will have an additional bit
    +        if (fb == 1) {
    +            fb = 2;
    +        }
    +        efb = encodeBitWidth(fb) << 1;
    +        len = variableRunLength - 1;
    +        variableRunLength = 0;
    +    }
    +
    +    // extract the 9th bit of run length
    +    const uint32_t tailBits = (len & 0x100) >> 8;
    +
    +    // create first byte of the header
    +    const char headerFirstByte = static_cast<char>(getOpCode(DELTA) | efb | tailBits);
    +
    +    // second byte of the header stores the remaining 8 bits of runlength
    +    const char headerSecondByte = static_cast<char>(len & 0xff);
    +
    +    // write header
    +    writeByte(headerFirstByte);
    +    writeByte(headerSecondByte);
    +
    +    // store the first value from zigzag literal array
    +    if (isSigned) {
    +        writeVslong(literals[0]);
    +    } else {
    +        writeVulong(literals[0]);
    +    }
    +
    +    if (option.isFixedDelta) {
    +        // if delta is fixed then we don't need to store delta blob
    +        writeVslong(option.fixedDelta);
    +    } else {
    +        // store the first value as delta value using zigzag encoding
    +        writeVslong(adjDeltas[0]);
    +
    +        // adjacent delta values are bit packed. The length of adjDeltas array is
    +        // always one less than the number of literals (delta difference for n
    +        // elements is n-1). We have already written one element, write the
    +        // remaining numLiterals - 2 elements here
    +        writeInts(adjDeltas, 1, numLiterals - 2, fb);
    +    }
    +}
    +
    +void RleEncoderV2::writeInts(int64_t* input, uint32_t offset, size_t len, uint32_t bitSize)
{
    +  if(input == nullptr || len < 1 || bitSize < 1) {
    +      return;
    +  }
    +
    +  if (getClosestAlignedFixedBits(bitSize) == bitSize) {
    +    uint32_t numBytes;
    +    uint32_t endOffSet = static_cast<uint32_t>(offset + len);
    +    if (bitSize < 8 ) {;
    +      char bitMask = static_cast<char>((1 << bitSize) - 1);
    +      uint32_t numHops = 8 / bitSize;
    +      uint32_t remainder = static_cast<uint32_t>(len % numHops);
    +      uint32_t endUnroll = endOffSet - remainder;
    +      for (uint32_t i = offset; i < endUnroll; i+=numHops) {
    +        char toWrite = 0;
    +        for (uint32_t j = 0; j < numHops; ++j) {
    +          toWrite |= static_cast<char>((input[i+j] & bitMask) << (8 -
(j + 1) * bitSize));
    +        }
    +        writeByte(toWrite);
    +      }
    +
    +      if (remainder > 0) {
    +        uint32_t startShift = 8 - bitSize;
    +        char toWrite = 0;
    +        for (uint32_t i = endUnroll; i < endOffSet; ++i) {
    +          toWrite |= static_cast<char>((input[i] & bitMask) << startShift);
    +          startShift -= bitSize;
    +        }
    +        writeByte(toWrite);
    +      }
    +
    +    } else {
    +      numBytes = bitSize / 8;
    +
    +      for (uint32_t i = offset; i < endOffSet; ++i) {
    +        for (uint32_t j = 0; j < numBytes; ++j) {
    +          char toWrite = static_cast<char>((input[i] >> (8 * (numBytes -
j - 1))) & 255);
    +          writeByte(toWrite);
    +        }
    +      }
    +    }
    +
    +    return;
    +  }
    +
    +  // write for unaligned bit size
    +  uint32_t bitsLeft = 8;
    +  char current = 0;
    +  for(uint32_t i = offset; i < (offset + len); i++) {
    +    long value = input[i];
    --- End diff --
    
    int64_t value


---

Mime
View raw message