presto-orc/src/main/java/io/prestosql/orc/stream/LongOutputStreamV2.java/LongOutputStreamV2/preparePatchedBlob
class LongOutputStreamV2:    private void preparePatchedBlob()
    {
        // mask will be max value beyond which patch will be generated
        long mask = (1L << brBits95p) - 1;

        // since we are considering only 95 percentile, the size of gap and
        // patch array can contain only be 5% values
        patchLength = (int) Math.ceil((numLiterals * 0.05));

        int[] gapList = new int[patchLength];
        long[] patchList = new long[patchLength];

        // #bit for patch
        patchWidth = brBits100p - brBits95p;
        patchWidth = getClosestFixedBits(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 (patchWidth == 64) {
            patchWidth = 56;
            brBits95p = 8;
            mask = (1L << brBits95p) - 1;
        }

        int gapIdx = 0;
        int patchIdx = 0;
        int prev = 0;
        int gap;
        int maxGap = 0;

        for (int i = 0; i < numLiterals; i++) {
            // if value is above mask then create the patch and record the gap
            if (baseReducedLiterals[i] > mask) {
                gap = i - prev;
                if (gap > maxGap) {
                    maxGap = gap;
                }

                // gaps are relative, so store the previous patched value index
                prev = i;
                gapList[gapIdx++] = gap;

                // extract the most significant bits that are over mask bits
                long patch = baseReducedLiterals[i] >>> brBits95p;
                patchList[patchIdx++] = patch;

                // strip off the MSB to enable safe bit packing
                baseReducedLiterals[i] &= mask;
            }
        }

        // adjust the patch length to number of entries in gap list
        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 at least 1 bit
        if (maxGap == 0 && patchLength != 0) {
            patchGapWidth = 1;
        }
        else {
            patchGapWidth = findClosestNumBits(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 (patchGapWidth > 8) {
            patchGapWidth = 8;
            // for gap = 511, we need two additional entries in patch list
            if (maxGap == 511) {
                patchLength += 2;
            }
            else {
                patchLength += 1;
            }
        }

        // create gap vs patch list
        gapIdx = 0;
        patchIdx = 0;
        gapVsPatchList = new long[patchLength];
        for (int i = 0; i < patchLength; i++) {
            long g = gapList[gapIdx++];
            long p = patchList[patchIdx++];
            while (g > 255) {
                gapVsPatchList[i++] = (255L << patchWidth);
                g -= 255;
            }

            // store patch value in LSBs and gap in MSBs
            gapVsPatchList[i] = (g << patchWidth) | p;
        }
    }