view release on metacpan or  search on metacpan

ext/zstd/lib/legacy/zstd_v01.c  view on Meta::CPAN

typedef struct nodeElt_s {
    U32 count;
    U16 parent;
    BYTE byte;
    BYTE nbBits;
} nodeElt;


/* *******************************************************
*  Huff0 : Huffman block decompression
*********************************************************/
typedef struct {
    BYTE byte;
    BYTE nbBits;
} HUF_DElt;

static size_t HUF_readDTable (U16* DTable, const void* src, size_t srcSize)
{
    BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
    U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];  /* large enough for values from 0 to 16 */
    U32 weightTotal;
    U32 maxBits;
    const BYTE* ip = (const BYTE*) src;
    size_t iSize;
    size_t oSize;
    U32 n;
    U32 nextRankStart;
    void* ptr = DTable+1;
    HUF_DElt* const dt = (HUF_DElt*)ptr;

    if (!srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
    iSize = ip[0];

    FSE_STATIC_ASSERT(sizeof(HUF_DElt) == sizeof(U16));   /* if compilation fails here, assertion is false */
    //memset(huffWeight, 0, sizeof(huffWeight));   /* should not be necessary, but some analyzer complain ... */
    if (iSize >= 128)  /* special header */
    {
        if (iSize >= (242))   /* RLE */
        {
            static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
            oSize = l[iSize-242];
            memset(huffWeight, 1, sizeof(huffWeight));
            iSize = 0;
        }
        else   /* Incompressible */
        {
            oSize = iSize - 127;
            iSize = ((oSize+1)/2);
            if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
            ip += 1;
            for (n=0; n<oSize; n+=2)
            {
                huffWeight[n]   = ip[n/2] >> 4;
                huffWeight[n+1] = ip[n/2] & 15;
            }
        }
    }
    else  /* header compressed with FSE (normal case) */
    {
        if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
        oSize = FSE_decompress(huffWeight, HUF_MAX_SYMBOL_VALUE, ip+1, iSize);   /* max 255 values decoded, last one is implied */
        if (FSE_isError(oSize)) return oSize;
    }

    /* collect weight stats */
    memset(rankVal, 0, sizeof(rankVal));
    weightTotal = 0;
    for (n=0; n<oSize; n++)
    {
        if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return (size_t)-FSE_ERROR_corruptionDetected;
        rankVal[huffWeight[n]]++;
        weightTotal += (1 << huffWeight[n]) >> 1;
    }
    if (weightTotal == 0) return (size_t)-FSE_ERROR_corruptionDetected;

    /* get last non-null symbol weight (implied, total must be 2^n) */
    maxBits = FSE_highbit32(weightTotal) + 1;
    if (maxBits > DTable[0]) return (size_t)-FSE_ERROR_tableLog_tooLarge;   /* DTable is too small */
    DTable[0] = (U16)maxBits;
    {
        U32 total = 1 << maxBits;
        U32 rest = total - weightTotal;
        U32 verif = 1 << FSE_highbit32(rest);
        U32 lastWeight = FSE_highbit32(rest) + 1;
        if (verif != rest) return (size_t)-FSE_ERROR_corruptionDetected;    /* last value must be a clean power of 2 */
        huffWeight[oSize] = (BYTE)lastWeight;
        rankVal[lastWeight]++;
    }

    /* check tree construction validity */
    if ((rankVal[1] < 2) || (rankVal[1] & 1)) return (size_t)-FSE_ERROR_corruptionDetected;   /* by construction : at least 2 elts of rank 1, must be even */

    /* Prepare ranks */
    nextRankStart = 0;
    for (n=1; n<=maxBits; n++)
    {
        U32 current = nextRankStart;
        nextRankStart += (rankVal[n] << (n-1));
        rankVal[n] = current;
    }

    /* fill DTable */
    for (n=0; n<=oSize; n++)
    {
        const U32 w = huffWeight[n];
        const U32 length = (1 << w) >> 1;
        U32 i;
        HUF_DElt D;
        D.byte = (BYTE)n; D.nbBits = (BYTE)(maxBits + 1 - w);
        for (i = rankVal[w]; i < rankVal[w] + length; i++)
            dt[i] = D;
        rankVal[w] += length;
    }

    return iSize+1;
}


static BYTE HUF_decodeSymbol(FSE_DStream_t* Dstream, const HUF_DElt* dt, const U32 dtLog)
{
        const size_t val = FSE_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */

ext/zstd/lib/legacy/zstd_v01.c  view on Meta::CPAN

{
    BYTE* op = (BYTE*)dst;
    BYTE* const oend = op + maxDstSize;
    const BYTE* ip = (const BYTE*)src;
    size_t errorCode;
    size_t litSize;

    /* check : minimum 2, for litSize, +1, for content */
    if (srcSize <= 3) return ERROR(corruption_detected);

    litSize = ip[1] + (ip[0]<<8);
    litSize += ((ip[-3] >> 3) & 7) << 16;   /* mmmmh.... */
    op = oend - litSize;

    (void)ctx;
    if (litSize > maxDstSize) return ERROR(dstSize_tooSmall);
    errorCode = HUF_decompress(op, litSize, ip+2, srcSize-2);
    if (FSE_isError(errorCode)) return ERROR(GENERIC);
    return litSize;
}


static size_t ZSTDv01_decodeLiteralsBlock(void* ctx,
                                void* dst, size_t maxDstSize,
                          const BYTE** litStart, size_t* litSize,
                          const void* src, size_t srcSize)
{
    const BYTE* const istart = (const BYTE* const)src;
    const BYTE* ip = istart;
    BYTE* const ostart = (BYTE* const)dst;
    BYTE* const oend = ostart + maxDstSize;
    blockProperties_t litbp;

    size_t litcSize = ZSTDv01_getcBlockSize(src, srcSize, &litbp);
    if (ZSTDv01_isError(litcSize)) return litcSize;
    if (litcSize > srcSize - ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
    ip += ZSTD_blockHeaderSize;

    switch(litbp.blockType)
    {
    case bt_raw:
        *litStart = ip;
        ip += litcSize;
        *litSize = litcSize;
        break;
    case bt_rle:
        {
            size_t rleSize = litbp.origSize;
            if (rleSize>maxDstSize) return ERROR(dstSize_tooSmall);
            if (!srcSize) return ERROR(srcSize_wrong);
            if (rleSize > 0) {
                memset(oend - rleSize, *ip, rleSize);
            }
            *litStart = oend - rleSize;
            *litSize = rleSize;
            ip++;
            break;
        }
    case bt_compressed:
        {
            size_t decodedLitSize = ZSTD_decompressLiterals(ctx, dst, maxDstSize, ip, litcSize);
            if (ZSTDv01_isError(decodedLitSize)) return decodedLitSize;
            *litStart = oend - decodedLitSize;
            *litSize = decodedLitSize;
            ip += litcSize;
            break;
        }
    case bt_end:
    default:
        return ERROR(GENERIC);
    }

    return ip-istart;
}


static size_t ZSTDv01_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
                         FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
                         const void* src, size_t srcSize)
{
    const BYTE* const istart = (const BYTE* const)src;
    const BYTE* ip = istart;
    const BYTE* const iend = istart + srcSize;
    U32 LLtype, Offtype, MLtype;
    U32 LLlog, Offlog, MLlog;
    size_t dumpsLength;

    /* check */
    if (srcSize < 5) return ERROR(srcSize_wrong);

    /* SeqHead */
    *nbSeq = ZSTD_readLE16(ip); ip+=2;
    LLtype  = *ip >> 6;
    Offtype = (*ip >> 4) & 3;
    MLtype  = (*ip >> 2) & 3;
    if (*ip & 2)
    {
        dumpsLength  = ip[2];
        dumpsLength += ip[1] << 8;
        ip += 3;
    }
    else
    {
        dumpsLength  = ip[1];
        dumpsLength += (ip[0] & 1) << 8;
        ip += 2;
    }
    *dumpsPtr = ip;
    ip += dumpsLength;
    *dumpsLengthPtr = dumpsLength;

    /* check */
    if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */

    /* sequences */
    {
        S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL and MaxOff */
        size_t headerSize;

        /* Build DTables */
        switch(LLtype)
        {
        case bt_rle :
            LLlog = 0;