presto-orc/src/main/java/io/prestosql/orc/stream/LongOutputStreamV2.java/LongOutputStreamV2/determineEncoding
class LongOutputStreamV2:    private EncodingType determineEncoding()
    {
        // we need to compute zigzag values for DIRECT encoding if we decide to
        // break early for delta overflows or for shorter runs
        if (signed) {
            for (int i1 = 0; i1 < numLiterals; i1++) {
                zigzagLiterals[i1] = zigzagEncode(literals[i1]);
            }
        }
        else {
            System.arraycopy(literals, 0, zigzagLiterals, 0, numLiterals);
        }

        zzBits100p = percentileBits(zigzagLiterals, 0, numLiterals, 1.0);

        // not a big win for shorter runs to determine encoding
        if (numLiterals <= MIN_REPEAT) {
            return EncodingType.DIRECT;
        }

        // DELTA encoding check

        // for identifying monotonic sequences
        boolean isIncreasing = true;
        boolean isDecreasing = true;
        this.isFixedDelta = true;

        this.min = literals[0];
        long max = literals[0];
        final long initialDelta = literals[1] - literals[0];
        long currDelta = initialDelta;
        long deltaMax = initialDelta;
        this.adjDeltas[0] = initialDelta;

        for (int i = 1; i < numLiterals; i++) {
            final long l1 = literals[i];
            final long l0 = literals[i - 1];
            currDelta = l1 - l0;
            min = Math.min(min, l1);
            max = Math.max(max, l1);

            isIncreasing &= (l0 <= l1);
            isDecreasing &= (l0 >= l1);

            isFixedDelta &= (currDelta == initialDelta);
            if (i > 1) {
                adjDeltas[i - 1] = Math.abs(currDelta);
                deltaMax = Math.max(deltaMax, adjDeltas[i - 1]);
            }
        }

        // its 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, min)) {
            return EncodingType.DIRECT;
        }

        // invariant - subtracting any number from any other in the literals after
        // this point won't overflow

        // if initialDelta is 0 then we cannot delta encode as we cannot identify
        // the sign of deltas (increasing or decreasing)
        if (initialDelta != 0) {
            // if min is equal to max then the delta is 0, this condition happens for
            // fixed values run >10 which cannot be encoded with SHORT_REPEAT
            if (min == max) {
                throw new IllegalStateException("currDelta should be zero");
            }

            if (isFixedDelta) {
                fixedDelta = currDelta;
                return EncodingType.DELTA;
            }

            // stores the number of bits required for packing delta blob in
            // delta encoding
            bitsDeltaMax = findClosestNumBits(deltaMax);

            // monotonic condition
            if (isIncreasing || isDecreasing) {
                return EncodingType.DELTA;
            }
        }

        // 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
        zzBits90p = percentileBits(zigzagLiterals, 0, numLiterals, 0.9);

        // if difference in bits between 95th percentile and 100th percentile
        // of zigzag encoded values is 0 or 1, then the patch length will be 0,
        // so just use direct
        if (zzBits100p - zzBits90p <= 1) {
            return EncodingType.DIRECT;
        }

        // patching is done only on base reduced values.
        // remove base from literals
        for (int i = 0; i < numLiterals; i++) {
            baseReducedLiterals[i] = literals[i] - min;
        }

        // 95th percentile width is used to determine max allowed value
        // after which patching will be done
        brBits95p = percentileBits(baseReducedLiterals, 0, numLiterals, 0.95);

        // 100th percentile is used to compute the max patch width
        brBits100p = percentileBits(baseReducedLiterals, 0, numLiterals, 1.0);

        // check again if patching will be effective using base reduced values.
        if (brBits100p == brBits95p) {
            return EncodingType.DIRECT;
        }

        return EncodingType.PATCHED_BASE;
    }