/src/wavpack/src/read_words.c

Source (jump to first uncovered line)
////////////////////////////////////////////////////////////////////////////
//                           **** WAVPACK ****                            //
//                  Hybrid Lossless Wavefile Compressor                   //
//              Copyright (c) 1998 - 2013 Conifer Software.               //
//                          All Rights Reserved.                          //
//      Distributed under the BSD Software License (see license.txt)      //
////////////////////////////////////////////////////////////////////////////

// read_words.c

// This module provides entropy word decoding functions using
// a variation on the Rice method.  This was introduced in version 3.93
// because it allows splitting the data into a "lossy" stream and a
// "correction" stream in a very efficient manner and is therefore ideal
// for the "hybrid" mode.  For 4.0, the efficiency of this method was
// significantly improved by moving away from the normal Rice restriction of
// using powers of two for the modulus divisions and now the method can be
// used for both hybrid and pure lossless encoding.

// Samples are divided by median probabilities at 5/7 (71.43%), 10/49 (20.41%),
// and 20/343 (5.83%). Each zone has 3.5 times fewer samples than the
// previous. Using standard Rice coding on this data would result in 1.4
// bits per sample average (not counting sign bit). However, there is a
// very simple encoding that is over 99% efficient with this data and
// results in about 1.22 bits per sample.

#include <stdlib.h>
#include <string.h>

#include "wavpack_local.h"

#if defined (HAVE___BUILTIN_CTZ) || defined (_WIN64)
#define USE_CTZ_OPTIMIZATION    // use ctz intrinsic (or Windows equivalent) to count trailing ones
#elif defined(__WATCOMC__) && defined(__386__)
#define USE_CTZ_OPTIMIZATION
extern __inline uint32_t _bsf_watcom (uint32_t);
#pragma aux _bsf_watcom = \
  "bsf eax, eax" \
  parm [eax] nomemory \
  value [eax] \
  modify exact [eax] nomemory;
#else
#define USE_NEXT8_OPTIMIZATION  // optimization using a table to count trailing ones
#endif

#define USE_BITMASK_TABLES      // use tables instead of shifting for certain masking operations

///////////////////////////// local table storage ////////////////////////////

#ifdef USE_NEXT8_OPTIMIZATION
static const char ones_count_table [] = {
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
    0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,8
};
#endif

///////////////////////////// executable code ////////////////////////////////

static uint32_t __inline read_code (Bitstream *bs, uint32_t maxcode);

// Read the next word from the bitstream "wvbits" and return the value. This
// function can be used for hybrid or lossless streams, but since an
// optimized version is available for lossless this function would normally
// be used for hybrid only. If a hybrid lossless stream is being read then
// the "correction" offset is written at the specified pointer. A return value
// of WORD_EOF indicates that the end of the bitstream was reached (all 1s) or
// some other error occurred.

int32_t FASTCALL get_word (WavpackStream *wps, int chan, int32_t *correction)
{
    struct entropy_data *c = wps->w.c + chan;
    uint32_t ones_count, low, mid, high;
    int32_t value;
    int sign;

    if (!wps->wvbits.ptr)
        return WORD_EOF;

    if (correction)
        *correction = 0;

    if (!(wps->w.c [0].median [0] & ~1) && !wps->w.holding_zero && !wps->w.holding_one && !(wps->w.c [1].median [0] & ~1)) {
        uint32_t mask;
        int cbits;

        if (wps->w.zeros_acc) {
            if (--wps->w.zeros_acc) {
                c->slow_level -= (c->slow_level + SLO) >> SLS;
                return 0;
            }
        }
        else {
            for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);

            if (cbits == 33)
                return WORD_EOF;

            if (cbits < 2)
                wps->w.zeros_acc = cbits;
            else {
                for (mask = 1, wps->w.zeros_acc = 0; --cbits; mask <<= 1)
                    if (getbit (&wps->wvbits))
                        wps->w.zeros_acc |= mask;

                wps->w.zeros_acc |= mask;
            }

            if (wps->w.zeros_acc) {
                c->slow_level -= (c->slow_level + SLO) >> SLS;
                CLEAR (wps->w.c [0].median);
                CLEAR (wps->w.c [1].median);
                return 0;
            }
        }
    }

    if (wps->w.holding_zero)
        ones_count = wps->w.holding_zero = 0;
    else {
#ifdef USE_CTZ_OPTIMIZATION
        while (wps->wvbits.bc < LIMIT_ONES) {
            if (++(wps->wvbits.ptr) == wps->wvbits.end)
                wps->wvbits.wrap (&wps->wvbits);

            wps->wvbits.sr |= *(wps->wvbits.ptr) << wps->wvbits.bc;
            wps->wvbits.bc += sizeof (*(wps->wvbits.ptr)) * 8;
        }

#ifdef _MSC_VER
        { unsigned long res; _BitScanForward (&res, (unsigned long)~wps->wvbits.sr); ones_count = (uint32_t) res; }
#elif defined(__WATCOMC__) && defined(__386__)
        ones_count = _bsf_watcom (~wps->wvbits.sr);
#else
        ones_count = __builtin_ctz (~wps->wvbits.sr);
#endif

        if (ones_count >= LIMIT_ONES) {
            wps->wvbits.bc -= ones_count;
            wps->wvbits.sr >>= ones_count;

            for (; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count);

            if (ones_count == (LIMIT_ONES + 1))
                return WORD_EOF;

            if (ones_count == LIMIT_ONES) {
                uint32_t mask;
                int cbits;

                for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);

                if (cbits == 33)
                    return WORD_EOF;

                if (cbits < 2)
                    ones_count = cbits;
                else {
                    for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
                        if (getbit (&wps->wvbits))
                            ones_count |= mask;

                    ones_count |= mask;
                }

                ones_count += LIMIT_ONES;
            }
        }
        else {
            wps->wvbits.bc -= ones_count + 1;
            wps->wvbits.sr >>= ones_count + 1;
        }
#elif defined (USE_NEXT8_OPTIMIZATION)
        int next8;

        if (wps->wvbits.bc < 8) {
            if (++(wps->wvbits.ptr) == wps->wvbits.end)
                wps->wvbits.wrap (&wps->wvbits);

            next8 = (wps->wvbits.sr |= *(wps->wvbits.ptr) << wps->wvbits.bc) & 0xff;
            wps->wvbits.bc += sizeof (*(wps->wvbits.ptr)) * 8;
        }
        else
            next8 = wps->wvbits.sr & 0xff;

        if (next8 == 0xff) {
            wps->wvbits.bc -= 8;
            wps->wvbits.sr >>= 8;

            for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count);

            if (ones_count == (LIMIT_ONES + 1))
                return WORD_EOF;

            if (ones_count == LIMIT_ONES) {
                uint32_t mask;
                int cbits;

                for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);

                if (cbits == 33)
                    return WORD_EOF;

                if (cbits < 2)
                    ones_count = cbits;
                else {
                    for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
                        if (getbit (&wps->wvbits))
                            ones_count |= mask;

                    ones_count |= mask;
                }

                ones_count += LIMIT_ONES;
            }
        }
        else {
            wps->wvbits.bc -= (ones_count = ones_count_table [next8]) + 1;
            wps->wvbits.sr >>= ones_count + 1;
        }
#else
        for (ones_count = 0; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count);

        if (ones_count >= LIMIT_ONES) {
            uint32_t mask;
            int cbits;

            if (ones_count == (LIMIT_ONES + 1))
                return WORD_EOF;

            for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);

            if (cbits == 33)
                return WORD_EOF;

            if (cbits < 2)
                ones_count = cbits;
            else {
                for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
                    if (getbit (&wps->wvbits))
                        ones_count |= mask;

                ones_count |= mask;
            }

            ones_count += LIMIT_ONES;
        }
#endif

        if (wps->w.holding_one) {
            wps->w.holding_one = ones_count & 1;
            ones_count = (ones_count >> 1) + 1;
        }
        else {
            wps->w.holding_one = ones_count & 1;
            ones_count >>= 1;
        }

        wps->w.holding_zero = ~wps->w.holding_one & 1;
    }

    if ((wps->wphdr.flags & HYBRID_FLAG) && !chan)
        update_error_limit (wps);

    if (ones_count == 0) {
        low = 0;
        high = GET_MED (0) - 1;
        DEC_MED0 ();
    }
    else {
        low = GET_MED (0);
        INC_MED0 ();

        if (ones_count == 1) {
            high = low + GET_MED (1) - 1;
            DEC_MED1 ();
        }
        else {
            low += GET_MED (1);
            INC_MED1 ();

            if (ones_count == 2) {
                high = low + GET_MED (2) - 1;
                DEC_MED2 ();
            }
            else {
                low += (ones_count - 2) * GET_MED (2);
                high = low + GET_MED (2) - 1;
                INC_MED2 ();
            }
        }
    }

    low &= 0x7fffffff;
    high &= 0x7fffffff;

    if (low > high)         // make sure high and low make sense
        high = low;

    mid = (high + low + 1) >> 1;

    if (!c->error_limit)
        mid = read_code (&wps->wvbits, high - low) + low;
    else while (high - low > c->error_limit) {
        if (getbit (&wps->wvbits))
            mid = (high + (low = mid) + 1) >> 1;
        else
            mid = ((high = mid - 1) + low + 1) >> 1;
    }

    sign = getbit (&wps->wvbits);

    if (bs_is_open (&wps->wvcbits) && c->error_limit) {
        value = read_code (&wps->wvcbits, high - low) + low;

        if (correction)
            *correction = sign ? (mid - value) : (value - mid);
    }

    if (wps->wphdr.flags & HYBRID_BITRATE) {
        c->slow_level -= (c->slow_level + SLO) >> SLS;
        c->slow_level += wp_log2 (mid);
    }

    return sign ? ~mid : mid;
}

// This is an optimized version of get_word() that is used for lossless only
// (error_limit == 0). Also, rather than obtaining a single sample, it can be
// used to obtain an entire buffer of either mono or stereo samples.

int32_t get_words_lossless (WavpackStream *wps, int32_t *buffer, int32_t nsamples)
{
    struct entropy_data *c = wps->w.c;
    uint32_t ones_count, low, high;
    Bitstream *bs = &wps->wvbits;
    int32_t csamples;
#ifdef USE_NEXT8_OPTIMIZATION
    int32_t next8;
#endif

    if (nsamples && !bs->ptr) {
        memset (buffer, 0, (wps->wphdr.flags & MONO_DATA) ? nsamples * 4 : nsamples * 8);
        return nsamples;
    }

    if (!(wps->wphdr.flags & MONO_DATA))
        nsamples *= 2;

    for (csamples = 0; csamples < nsamples; ++csamples) {
        if (!(wps->wphdr.flags & MONO_DATA))
            c = wps->w.c + (csamples & 1);

        if (wps->w.holding_zero) {
            wps->w.holding_zero = 0;
            low = read_code (bs, GET_MED (0) - 1);
            DEC_MED0 ();
            buffer [csamples] = (getbit (bs)) ? ~low : low;

            if (++csamples == nsamples)
                break;

            if (!(wps->wphdr.flags & MONO_DATA))
                c = wps->w.c + (csamples & 1);
        }

        if (wps->w.c [0].median [0] < 2 && !wps->w.holding_one && wps->w.c [1].median [0] < 2) {
            uint32_t mask;
            int cbits;

            if (wps->w.zeros_acc) {
                if (--wps->w.zeros_acc) {
                    buffer [csamples] = 0;
                    continue;
                }
            }
            else {
                for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);

                if (cbits == 33)
                    break;

                if (cbits < 2)
                    wps->w.zeros_acc = cbits;
                else {
                    for (mask = 1, wps->w.zeros_acc = 0; --cbits; mask <<= 1)
                        if (getbit (bs))
                            wps->w.zeros_acc |= mask;

                    wps->w.zeros_acc |= mask;
                }

                if (wps->w.zeros_acc) {
                    CLEAR (wps->w.c [0].median);
                    CLEAR (wps->w.c [1].median);
                    buffer [csamples] = 0;
                    continue;
                }
            }
        }

#ifdef USE_CTZ_OPTIMIZATION
        while (bs->bc < LIMIT_ONES) {
            if (++(bs->ptr) == bs->end)
                bs->wrap (bs);

            bs->sr |= *(bs->ptr) << bs->bc;
            bs->bc += sizeof (*(bs->ptr)) * 8;
        }

#ifdef _MSC_VER
        { unsigned long res; _BitScanForward (&res, (unsigned long)~wps->wvbits.sr); ones_count = (uint32_t) res; }
#elif defined(__WATCOMC__) && defined(__386__)
        ones_count = _bsf_watcom (~wps->wvbits.sr);
#else
        ones_count = __builtin_ctz (~wps->wvbits.sr);
#endif

        if (ones_count >= LIMIT_ONES) {
            bs->bc -= ones_count;
            bs->sr >>= ones_count;

            for (; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);

            if (ones_count == (LIMIT_ONES + 1))
                break;

            if (ones_count == LIMIT_ONES) {
                uint32_t mask;
                int cbits;

                for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);

                if (cbits == 33)
                    break;

                if (cbits < 2)
                    ones_count = cbits;
                else {
                    for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
                        if (getbit (bs))
                            ones_count |= mask;

                    ones_count |= mask;
                }

                ones_count += LIMIT_ONES;
            }
        }
        else {
            bs->bc -= ones_count + 1;
            bs->sr >>= ones_count + 1;
        }
#elif defined (USE_NEXT8_OPTIMIZATION)
        if (bs->bc < 8) {
            if (++(bs->ptr) == bs->end)
                bs->wrap (bs);

            next8 = (bs->sr |= *(bs->ptr) << bs->bc) & 0xff;
            bs->bc += sizeof (*(bs->ptr)) * 8;
        }
        else
            next8 = bs->sr & 0xff;

        if (next8 == 0xff) {
            bs->bc -= 8;
            bs->sr >>= 8;

            for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);

            if (ones_count == (LIMIT_ONES + 1))
                break;

            if (ones_count == LIMIT_ONES) {
                uint32_t mask;
                int cbits;

                for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);

                if (cbits == 33)
                    break;

                if (cbits < 2)
                    ones_count = cbits;
                else {
                    for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
                        if (getbit (bs))
                            ones_count |= mask;

                    ones_count |= mask;
                }

                ones_count += LIMIT_ONES;
            }
        }
        else {
            bs->bc -= (ones_count = ones_count_table [next8]) + 1;
            bs->sr >>= ones_count + 1;
        }
#else
        for (ones_count = 0; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);

        if (ones_count >= LIMIT_ONES) {
            uint32_t mask;
            int cbits;

            if (ones_count == (LIMIT_ONES + 1))
                break;

            for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);

            if (cbits == 33)
                break;

            if (cbits < 2)
                ones_count = cbits;
            else {
                for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
                    if (getbit (bs))
                        ones_count |= mask;

                ones_count |= mask;
            }

            ones_count += LIMIT_ONES;
        }
#endif

        low = wps->w.holding_one;
        wps->w.holding_one = ones_count & 1;
        wps->w.holding_zero = ~ones_count & 1;
        ones_count = (ones_count >> 1) + low;

        if (ones_count == 0) {
            low = 0;
            high = GET_MED (0) - 1;
            DEC_MED0 ();
        }
        else {
            low = GET_MED (0);
            INC_MED0 ();

            if (ones_count == 1) {
                high = low + GET_MED (1) - 1;
                DEC_MED1 ();
            }
            else {
                low += GET_MED (1);
                INC_MED1 ();

                if (ones_count == 2) {
                    high = low + GET_MED (2) - 1;
                    DEC_MED2 ();
                }
                else {
                    low += (ones_count - 2) * GET_MED (2);
                    high = low + GET_MED (2) - 1;
                    INC_MED2 ();
                }
            }
        }

        low += read_code (bs, high - low);
        buffer [csamples] = (getbit (bs)) ? ~low : low;
    }

    return (wps->wphdr.flags & MONO_DATA) ? csamples : (csamples / 2);
}

// Read a single unsigned value from the specified bitstream with a value
// from 0 to maxcode. If there are exactly a power of two number of possible
// codes then this will read a fixed number of bits; otherwise it reads the
// minimum number of bits and then determines whether another bit is needed
// to define the code.

static uint32_t __inline read_code (Bitstream *bs, uint32_t maxcode)
{
    unsigned long local_sr;
    uint32_t extras, code;
    int bitcount;

    if (maxcode < 2)
        return maxcode ? getbit (bs) : 0;

    bitcount = count_bits (maxcode);
#ifdef USE_BITMASK_TABLES
    extras = bitset [bitcount] - maxcode - 1;
#else
    extras = (1 << bitcount) - maxcode - 1;
#endif

    local_sr = bs->sr;

    while (bs->bc < bitcount) {
        if (++(bs->ptr) == bs->end)
            bs->wrap (bs);

        local_sr |= (long)*(bs->ptr) << bs->bc;
        bs->bc += sizeof (*(bs->ptr)) * 8;
    }

#ifdef USE_BITMASK_TABLES
    if ((code = local_sr & bitmask [bitcount - 1]) >= extras)
#else
    if ((code = local_sr & ((1 << (bitcount - 1)) - 1)) >= extras)
#endif
        code = (code << 1) - extras + ((local_sr >> (bitcount - 1)) & 1);
    else
        bitcount--;

    if (sizeof (local_sr) < 8 && bs->bc > sizeof (local_sr) * 8) {
        bs->bc -= bitcount;
        bs->sr = *(bs->ptr) >> (sizeof (*(bs->ptr)) * 8 - bs->bc);
    }
    else {
        bs->bc -= bitcount;
        bs->sr = local_sr >> bitcount;
    }

    return code;
}

Coverage Report

Created: 2023-06-07 06:30

Line	Count	Source (jump to first uncovered line)
1		////////////////////////////////////////////////////////////////////////////
2		// ** WAVPACK ** //
3		// Hybrid Lossless Wavefile Compressor //
4		// Copyright (c) 1998 - 2013 Conifer Software. //
5		// All Rights Reserved. //
6		// Distributed under the BSD Software License (see license.txt) //
7		////////////////////////////////////////////////////////////////////////////
8
9		// read_words.c
10
11		// This module provides entropy word decoding functions using
12		// a variation on the Rice method. This was introduced in version 3.93
13		// because it allows splitting the data into a "lossy" stream and a
14		// "correction" stream in a very efficient manner and is therefore ideal
15		// for the "hybrid" mode. For 4.0, the efficiency of this method was
16		// significantly improved by moving away from the normal Rice restriction of
17		// using powers of two for the modulus divisions and now the method can be
18		// used for both hybrid and pure lossless encoding.
19
20		// Samples are divided by median probabilities at 5/7 (71.43%), 10/49 (20.41%),
21		// and 20/343 (5.83%). Each zone has 3.5 times fewer samples than the
22		// previous. Using standard Rice coding on this data would result in 1.4
23		// bits per sample average (not counting sign bit). However, there is a
24		// very simple encoding that is over 99% efficient with this data and
25		// results in about 1.22 bits per sample.
26
27		#include <stdlib.h>
28		#include <string.h>
29
30		#include "wavpack_local.h"
31
32		#if defined (HAVE___BUILTIN_CTZ) \|\| defined (_WIN64)
33		#define USE_CTZ_OPTIMIZATION // use ctz intrinsic (or Windows equivalent) to count trailing ones
34		#elif defined(__WATCOMC__) && defined(__386__)
35		#define USE_CTZ_OPTIMIZATION
36		extern __inline uint32_t _bsf_watcom (uint32_t);
37		#pragma aux _bsf_watcom = \
38		"bsf eax, eax" \
39		parm [eax] nomemory \
40		value [eax] \
41		modify exact [eax] nomemory;
42		#else
43		#define USE_NEXT8_OPTIMIZATION // optimization using a table to count trailing ones
44		#endif
45
46		#define USE_BITMASK_TABLES // use tables instead of shifting for certain masking operations
47
48		///////////////////////////// local table storage ////////////////////////////
49
50		#ifdef USE_NEXT8_OPTIMIZATION
51		static const char ones_count_table [] = {
52		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
53		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
54		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
55		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,
56		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
57		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
58		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
59		0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,8
60		};
61		#endif
62
63		///////////////////////////// executable code ////////////////////////////////
64
65		static uint32_t __inline read_code (Bitstream *bs, uint32_t maxcode);
66
67		// Read the next word from the bitstream "wvbits" and return the value. This
68		// function can be used for hybrid or lossless streams, but since an
69		// optimized version is available for lossless this function would normally
70		// be used for hybrid only. If a hybrid lossless stream is being read then
71		// the "correction" offset is written at the specified pointer. A return value
72		// of WORD_EOF indicates that the end of the bitstream was reached (all 1s) or
73		// some other error occurred.
74
75		int32_t FASTCALL get_word (WavpackStream wps, int chan, int32_t correction)
76	134M	{
77	134M	struct entropy_data *c = wps->w.c + chan;
78	134M	uint32_t ones_count, low, mid, high;
79	134M	int32_t value;
80	134M	int sign;
81
82	134M	if (!wps->wvbits.ptr)
83	0	return WORD_EOF;
84
85	134M	if (correction)
86	0	*correction = 0;
87
88	134M	if (!(wps->w.c [0].median [0] & ~1) && !wps->w.holding_zero && !wps->w.holding_one && !(wps->w.c [1].median [0] & ~1)) {
89	45.6M	uint32_t mask;
90	45.6M	int cbits;
91
92	45.6M	if (wps->w.zeros_acc) {
93	33.0M	if (--wps->w.zeros_acc) {
94	27.3M	c->slow_level -= (c->slow_level + SLO) >> SLS;
95	27.3M	return 0;
96	27.3M	}
97	33.0M	}
98	12.5M	else {
99	21.8M	for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);
100
101	12.5M	if (cbits == 33)
102	1.11k	return WORD_EOF;
103
104	12.5M	if (cbits < 2)
105	9.90M	wps->w.zeros_acc = cbits;
106	2.66M	else {
107	6.15M	for (mask = 1, wps->w.zeros_acc = 0; --cbits; mask <<= 1)
108	3.48M	if (getbit (&wps->wvbits))
109	2.01M	wps->w.zeros_acc \|= mask;
110
111	2.66M	wps->w.zeros_acc \|= mask;
112	2.66M	}
113
114	12.5M	if (wps->w.zeros_acc) {
115	5.74M	c->slow_level -= (c->slow_level + SLO) >> SLS;
116	5.74M	CLEAR (wps->w.c [0].median);
117	5.74M	CLEAR (wps->w.c [1].median);
118	5.74M	return 0;
119	5.74M	}
120	12.5M	}
121	45.6M	}
122
123	101M	if (wps->w.holding_zero)
124	42.8M	ones_count = wps->w.holding_zero = 0;
125	58.8M	else {
126	58.8M	#ifdef USE_CTZ_OPTIMIZATION
127	79.6M	while (wps->wvbits.bc < LIMIT_ONES) {
128	20.7M	if (++(wps->wvbits.ptr) == wps->wvbits.end)
129	18.6M	wps->wvbits.wrap (&wps->wvbits);
130
131	20.7M	wps->wvbits.sr \|= *(wps->wvbits.ptr) << wps->wvbits.bc;
132	20.7M	wps->wvbits.bc += sizeof ((wps->wvbits.ptr)) 8;
133	20.7M	}
134
135		#ifdef _MSC_VER
136		{ unsigned long res; _BitScanForward (&res, (unsigned long)~wps->wvbits.sr); ones_count = (uint32_t) res; }
137		#elif defined(__WATCOMC__) && defined(__386__)
138		ones_count = _bsf_watcom (~wps->wvbits.sr);
139		#else
140	58.8M	ones_count = __builtin_ctz (~wps->wvbits.sr);
141	58.8M	#endif
142
143	58.8M	if (ones_count >= LIMIT_ONES) {
144	113k	wps->wvbits.bc -= ones_count;
145	113k	wps->wvbits.sr >>= ones_count;
146
147	113k	for (; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count);
148
149	113k	if (ones_count == (LIMIT_ONES + 1))
150	278	return WORD_EOF;
151
152	113k	if (ones_count == LIMIT_ONES) {
153	76.7k	uint32_t mask;
154	76.7k	int cbits;
155
156	665k	for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);
157
158	76.7k	if (cbits == 33)
159	218	return WORD_EOF;
160
161	76.4k	if (cbits < 2)
162	12.6k	ones_count = cbits;
163	63.8k	else {
164	576k	for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
165	512k	if (getbit (&wps->wvbits))
166	330k	ones_count \|= mask;
167
168	63.8k	ones_count \|= mask;
169	63.8k	}
170
171	76.4k	ones_count += LIMIT_ONES;
172	76.4k	}
173	113k	}
174	58.7M	else {
175	58.7M	wps->wvbits.bc -= ones_count + 1;
176	58.7M	wps->wvbits.sr >>= ones_count + 1;
177	58.7M	}
178		#elif defined (USE_NEXT8_OPTIMIZATION)
179		int next8;
180
181		if (wps->wvbits.bc < 8) {
182		if (++(wps->wvbits.ptr) == wps->wvbits.end)
183		wps->wvbits.wrap (&wps->wvbits);
184
185		next8 = (wps->wvbits.sr \|= *(wps->wvbits.ptr) << wps->wvbits.bc) & 0xff;
186		wps->wvbits.bc += sizeof ((wps->wvbits.ptr)) 8;
187		}
188		else
189		next8 = wps->wvbits.sr & 0xff;
190
191		if (next8 == 0xff) {
192		wps->wvbits.bc -= 8;
193		wps->wvbits.sr >>= 8;
194
195		for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count);
196
197		if (ones_count == (LIMIT_ONES + 1))
198		return WORD_EOF;
199
200		if (ones_count == LIMIT_ONES) {
201		uint32_t mask;
202		int cbits;
203
204		for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);
205
206		if (cbits == 33)
207		return WORD_EOF;
208
209		if (cbits < 2)
210		ones_count = cbits;
211		else {
212		for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
213		if (getbit (&wps->wvbits))
214		ones_count \|= mask;
215
216		ones_count \|= mask;
217		}
218
219		ones_count += LIMIT_ONES;
220		}
221		}
222		else {
223		wps->wvbits.bc -= (ones_count = ones_count_table [next8]) + 1;
224		wps->wvbits.sr >>= ones_count + 1;
225		}
226		#else
227		for (ones_count = 0; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count);
228
229		if (ones_count >= LIMIT_ONES) {
230		uint32_t mask;
231		int cbits;
232
233		if (ones_count == (LIMIT_ONES + 1))
234		return WORD_EOF;
235
236		for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits);
237
238		if (cbits == 33)
239		return WORD_EOF;
240
241		if (cbits < 2)
242		ones_count = cbits;
243		else {
244		for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
245		if (getbit (&wps->wvbits))
246		ones_count \|= mask;
247
248		ones_count \|= mask;
249		}
250
251		ones_count += LIMIT_ONES;
252		}
253		#endif
254
255	58.8M	if (wps->w.holding_one) {
256	16.0M	wps->w.holding_one = ones_count & 1;
257	16.0M	ones_count = (ones_count >> 1) + 1;
258	16.0M	}
259	42.8M	else {
260	42.8M	wps->w.holding_one = ones_count & 1;
261	42.8M	ones_count >>= 1;
262	42.8M	}
263
264	58.8M	wps->w.holding_zero = ~wps->w.holding_one & 1;
265	58.8M	}
266
267	101M	if ((wps->wphdr.flags & HYBRID_FLAG) && !chan)
268	63.0M	update_error_limit (wps);
269
270	101M	if (ones_count == 0) {
271	76.3M	low = 0;
272	76.3M	high = GET_MED (0) - 1;
273	76.3M	DEC_MED0 ();
274	76.3M	}
275	25.3M	else {
276	25.3M	low = GET_MED (0);
277	25.3M	INC_MED0 ();
278
279	25.3M	if (ones_count == 1) {
280	16.4M	high = low + GET_MED (1) - 1;
281	16.4M	DEC_MED1 ();
282	16.4M	}
283	8.89M	else {
284	8.89M	low += GET_MED (1);
285	8.89M	INC_MED1 ();
286
287	8.89M	if (ones_count == 2) {
288	5.87M	high = low + GET_MED (2) - 1;
289	5.87M	DEC_MED2 ();
290	5.87M	}
291	3.01M	else {
292	3.01M	low += (ones_count - 2) * GET_MED (2);
293	3.01M	high = low + GET_MED (2) - 1;
294	3.01M	INC_MED2 ();
295	3.01M	}
296	8.89M	}
297	25.3M	}
298
299	101M	low &= 0x7fffffff;
300	101M	high &= 0x7fffffff;
301
302	101M	if (low > high) // make sure high and low make sense
303	729	high = low;
304
305	101M	mid = (high + low + 1) >> 1;
306
307	101M	if (!c->error_limit)
308	42.2M	mid = read_code (&wps->wvbits, high - low) + low;
309	78.6M	else while (high - low > c->error_limit) {
310	19.1M	if (getbit (&wps->wvbits))
311	11.1M	mid = (high + (low = mid) + 1) >> 1;
312	7.99M	else
313	7.99M	mid = ((high = mid - 1) + low + 1) >> 1;
314	19.1M	}
315
316	101M	sign = getbit (&wps->wvbits);
317
318	101M	if (bs_is_open (&wps->wvcbits) && c->error_limit) {
319	1.11M	value = read_code (&wps->wvcbits, high - low) + low;
320
321	1.11M	if (correction)
322	0	*correction = sign ? (mid - value) : (value - mid);
323	1.11M	}
324
325	101M	if (wps->wphdr.flags & HYBRID_BITRATE) {
326	60.9M	c->slow_level -= (c->slow_level + SLO) >> SLS;
327	60.9M	c->slow_level += wp_log2 (mid);
328	60.9M	}
329
330	101M	return sign ? ~mid : mid;
331	101M	}
332
333		// This is an optimized version of get_word() that is used for lossless only
334		// (error_limit == 0). Also, rather than obtaining a single sample, it can be
335		// used to obtain an entire buffer of either mono or stereo samples.
336
337		int32_t get_words_lossless (WavpackStream wps, int32_t buffer, int32_t nsamples)
338	68.7k	{
339	68.7k	struct entropy_data *c = wps->w.c;
340	68.7k	uint32_t ones_count, low, high;
341	68.7k	Bitstream *bs = &wps->wvbits;
342	68.7k	int32_t csamples;
343		#ifdef USE_NEXT8_OPTIMIZATION
344		int32_t next8;
345		#endif
346
347	68.7k	if (nsamples && !bs->ptr) {
348	0	memset (buffer, 0, (wps->wphdr.flags & MONO_DATA) ? nsamples * 4 : nsamples * 8);
349	0	return nsamples;
350	0	}
351
352	68.7k	if (!(wps->wphdr.flags & MONO_DATA))
353	32.2k	nsamples *= 2;
354
355	76.5M	for (csamples = 0; csamples < nsamples; ++csamples) {
356	76.5M	if (!(wps->wphdr.flags & MONO_DATA))
357	49.7M	c = wps->w.c + (csamples & 1);
358
359	76.5M	if (wps->w.holding_zero) {
360	37.1M	wps->w.holding_zero = 0;
361	37.1M	low = read_code (bs, GET_MED (0) - 1);
362	37.1M	DEC_MED0 ();
363	37.1M	buffer [csamples] = (getbit (bs)) ? ~low : low;
364
365	37.1M	if (++csamples == nsamples)
366	22.3k	break;
367
368	37.1M	if (!(wps->wphdr.flags & MONO_DATA))
369	25.7M	c = wps->w.c + (csamples & 1);
370	37.1M	}
371
372	76.4M	if (wps->w.c [0].median [0] < 2 && !wps->w.holding_one && wps->w.c [1].median [0] < 2) {
373	34.3M	uint32_t mask;
374	34.3M	int cbits;
375
376	34.3M	if (wps->w.zeros_acc) {
377	24.8M	if (--wps->w.zeros_acc) {
378	22.0M	buffer [csamples] = 0;
379	22.0M	continue;
380	22.0M	}
381	24.8M	}
382	9.49M	else {
383	14.3M	for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);
384
385	9.49M	if (cbits == 33)
386	339	break;
387
388	9.49M	if (cbits < 2)
389	8.28M	wps->w.zeros_acc = cbits;
390	1.20M	else {
391	3.25M	for (mask = 1, wps->w.zeros_acc = 0; --cbits; mask <<= 1)
392	2.05M	if (getbit (bs))
393	757k	wps->w.zeros_acc \|= mask;
394
395	1.20M	wps->w.zeros_acc \|= mask;
396	1.20M	}
397
398	9.49M	if (wps->w.zeros_acc) {
399	2.79M	CLEAR (wps->w.c [0].median);
400	2.79M	CLEAR (wps->w.c [1].median);
401	2.79M	buffer [csamples] = 0;
402	2.79M	continue;
403	2.79M	}
404	9.49M	}
405	34.3M	}
406
407	51.6M	#ifdef USE_CTZ_OPTIMIZATION
408	78.5M	while (bs->bc < LIMIT_ONES) {
409	26.9M	if (++(bs->ptr) == bs->end)
410	17.0M	bs->wrap (bs);
411
412	26.9M	bs->sr \|= *(bs->ptr) << bs->bc;
413	26.9M	bs->bc += sizeof ((bs->ptr)) 8;
414	26.9M	}
415
416		#ifdef _MSC_VER
417		{ unsigned long res; _BitScanForward (&res, (unsigned long)~wps->wvbits.sr); ones_count = (uint32_t) res; }
418		#elif defined(__WATCOMC__) && defined(__386__)
419		ones_count = _bsf_watcom (~wps->wvbits.sr);
420		#else
421	51.6M	ones_count = __builtin_ctz (~wps->wvbits.sr);
422	51.6M	#endif
423
424	51.6M	if (ones_count >= LIMIT_ONES) {
425	94.8k	bs->bc -= ones_count;
426	94.8k	bs->sr >>= ones_count;
427
428	95.0k	for (; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);
429
430	94.8k	if (ones_count == (LIMIT_ONES + 1))
431	241	break;
432
433	94.5k	if (ones_count == LIMIT_ONES) {
434	76.6k	uint32_t mask;
435	76.6k	int cbits;
436
437	638k	for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);
438
439	76.6k	if (cbits == 33)
440	201	break;
441
442	76.4k	if (cbits < 2)
443	37.4k	ones_count = cbits;
444	38.9k	else {
445	546k	for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
446	507k	if (getbit (bs))
447	300k	ones_count \|= mask;
448
449	38.9k	ones_count \|= mask;
450	38.9k	}
451
452	76.4k	ones_count += LIMIT_ONES;
453	76.4k	}
454	94.5k	}
455	51.5M	else {
456	51.5M	bs->bc -= ones_count + 1;
457	51.5M	bs->sr >>= ones_count + 1;
458	51.5M	}
459		#elif defined (USE_NEXT8_OPTIMIZATION)
460		if (bs->bc < 8) {
461		if (++(bs->ptr) == bs->end)
462		bs->wrap (bs);
463
464		next8 = (bs->sr \|= *(bs->ptr) << bs->bc) & 0xff;
465		bs->bc += sizeof ((bs->ptr)) 8;
466		}
467		else
468		next8 = bs->sr & 0xff;
469
470		if (next8 == 0xff) {
471		bs->bc -= 8;
472		bs->sr >>= 8;
473
474		for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);
475
476		if (ones_count == (LIMIT_ONES + 1))
477		break;
478
479		if (ones_count == LIMIT_ONES) {
480		uint32_t mask;
481		int cbits;
482
483		for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);
484
485		if (cbits == 33)
486		break;
487
488		if (cbits < 2)
489		ones_count = cbits;
490		else {
491		for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
492		if (getbit (bs))
493		ones_count \|= mask;
494
495		ones_count \|= mask;
496		}
497
498		ones_count += LIMIT_ONES;
499		}
500		}
501		else {
502		bs->bc -= (ones_count = ones_count_table [next8]) + 1;
503		bs->sr >>= ones_count + 1;
504		}
505		#else
506		for (ones_count = 0; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count);
507
508		if (ones_count >= LIMIT_ONES) {
509		uint32_t mask;
510		int cbits;
511
512		if (ones_count == (LIMIT_ONES + 1))
513		break;
514
515		for (cbits = 0; cbits < 33 && getbit (bs); ++cbits);
516
517		if (cbits == 33)
518		break;
519
520		if (cbits < 2)
521		ones_count = cbits;
522		else {
523		for (mask = 1, ones_count = 0; --cbits; mask <<= 1)
524		if (getbit (bs))
525		ones_count \|= mask;
526
527		ones_count \|= mask;
528		}
529
530		ones_count += LIMIT_ONES;
531		}
532		#endif
533
534	51.6M	low = wps->w.holding_one;
535	51.6M	wps->w.holding_one = ones_count & 1;
536	51.6M	wps->w.holding_zero = ~ones_count & 1;
537	51.6M	ones_count = (ones_count >> 1) + low;
538
539	51.6M	if (ones_count == 0) {
540	29.6M	low = 0;
541	29.6M	high = GET_MED (0) - 1;
542	29.6M	DEC_MED0 ();
543	29.6M	}
544	22.0M	else {
545	22.0M	low = GET_MED (0);
546	22.0M	INC_MED0 ();
547
548	22.0M	if (ones_count == 1) {
549	13.6M	high = low + GET_MED (1) - 1;
550	13.6M	DEC_MED1 ();
551	13.6M	}
552	8.36M	else {
553	8.36M	low += GET_MED (1);
554	8.36M	INC_MED1 ();
555
556	8.36M	if (ones_count == 2) {
557	5.55M	high = low + GET_MED (2) - 1;
558	5.55M	DEC_MED2 ();
559	5.55M	}
560	2.80M	else {
561	2.80M	low += (ones_count - 2) * GET_MED (2);
562	2.80M	high = low + GET_MED (2) - 1;
563	2.80M	INC_MED2 ();
564	2.80M	}
565	8.36M	}
566	22.0M	}
567
568	51.6M	low += read_code (bs, high - low);
569	51.6M	buffer [csamples] = (getbit (bs)) ? ~low : low;
570	51.6M	}
571
572	68.7k	return (wps->wphdr.flags & MONO_DATA) ? csamples : (csamples / 2);
573	68.7k	}
574
575		// Read a single unsigned value from the specified bitstream with a value
576		// from 0 to maxcode. If there are exactly a power of two number of possible
577		// codes then this will read a fixed number of bits; otherwise it reads the
578		// minimum number of bits and then determines whether another bit is needed
579		// to define the code.
580
581		static uint32_t __inline read_code (Bitstream *bs, uint32_t maxcode)
582	132M	{
583	132M	unsigned long local_sr;
584	132M	uint32_t extras, code;
585	132M	int bitcount;
586
587	132M	if (maxcode < 2)
588	86.4M	return maxcode ? getbit (bs) : 0;
589
590	45.7M	bitcount = count_bits (maxcode);
591	45.7M	#ifdef USE_BITMASK_TABLES
592	45.7M	extras = bitset [bitcount] - maxcode - 1;
593		#else
594		extras = (1 << bitcount) - maxcode - 1;
595		#endif
596
597	45.7M	local_sr = bs->sr;
598
599	71.2M	while (bs->bc < bitcount) {
600	25.5M	if (++(bs->ptr) == bs->end)
601	16.0M	bs->wrap (bs);
602
603	25.5M	local_sr \|= (long)*(bs->ptr) << bs->bc;
604	25.5M	bs->bc += sizeof ((bs->ptr)) 8;
605	25.5M	}
606
607	45.7M	#ifdef USE_BITMASK_TABLES
608	45.7M	if ((code = local_sr & bitmask [bitcount - 1]) >= extras)
609		#else
610		if ((code = local_sr & ((1 << (bitcount - 1)) - 1)) >= extras)
611		#endif
612	28.0M	code = (code << 1) - extras + ((local_sr >> (bitcount - 1)) & 1);
613	17.6M	else
614	17.6M	bitcount--;
615
616	45.7M	if (sizeof (local_sr) < 8 && bs->bc > sizeof (local_sr) * 8) {
617	0	bs->bc -= bitcount;
618	0	bs->sr = (bs->ptr) >> (sizeof ((bs->ptr)) * 8 - bs->bc);
619	0	}
620	45.7M	else {
621	45.7M	bs->bc -= bitcount;
622	45.7M	bs->sr = local_sr >> bitcount;
623	45.7M	}
624
625	45.7M	return code;
626	132M	}