<commit_before>/*-
 * Copyright (c) 2014 <NAME>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this 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.
 */
package org.lbzip2.impl;

import static org.lbzip2.impl.Constants.MAX_CODE_LENGTH;
import static org.lbzip2.impl.Constants.crc_table;
import static org.lbzip2.impl.Constants.rand_table;
import static org.lbzip2.impl.MtfDecoder.CMAP_BASE;
import static org.lbzip2.impl.PrefixDecoder.EOB;
import static org.lbzip2.impl.PrefixDecoder.HUFF_START_WIDTH;
import static org.lbzip2.impl.PrefixDecoder.RUN_A;
import static org.lbzip2.impl.Unsigned.uge;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import org.lbzip2.StreamFormatException;

public class MBC
{
    private final InputStream in;

    private final OutputStream out;

    public MBC( InputStream in, OutputStream out )
    {
        this.in = in;
        this.out = out;
    }

    private static void err( String msg )
        throws StreamFormatException
    {
        throw new StreamFormatException( msg );
    }

    /* Read a single byte from stdin. */
    private int read()
        throws IOException
    {
        return in.read();
    }

    /* Write a single byte to stdout. */
    private void write( int c )
        throws IOException
    {
        out.write( c );
    }

    /* Print an error message and terminate. */
    private static void bad()
        throws StreamFormatException
    {
        err( "Data error" );
    }

    private long bb; /* the bit-buffer (left-justified) */

    private int bk; /* number of bits remaining in the `bb' bit-buffer */

    private final int[] tt = new int[900000]; /* IBWT linked cyclic list */

    private int crc; /* CRC32 computed so far */

    private int mbs; /* maximal block size (100k-900k in 100k steps) */

    private boolean rnd; /* is current block randomized? (0 or 1) */

    private int bs; /* current block size (1-900000) */

    private int idx; /* BWT primary index (0-899999) */

    private int as; /*
                     * alphabet size (number of distinct prefix codes, 3-258)
                     */

    private int nt; /*
                     * number of prefix trees used for current block (2-6)
                     */

    private int ns; /* number of selectors (1-32767) */

    private int nm; /* number of MTF values */

    private final byte[] blk = new byte[900000]; /* reconstructed block */

    private final byte[][] len = new byte[6][259]; /*
                                                    * code lengths for different trees (element 258 is a sentinel)
                                                    */

    private final byte[] sel = new byte[32767]; /* selector MTF values */

    private final MtfDecoder mtf = new MtfDecoder();

    private final PrefixDecoder pd = new PrefixDecoder();

    private final short[] mv = new short[900050]; /*
                                                   * MTF values (elements 900000-900049 are sentinels)
                                                   */

    private void need( int n )
        throws StreamFormatException, IOException
    {
        while ( bk < n )
        {
            long c = in.read();
            if ( c < 0 )
                bad();
            bk += 8;
            bb += c << ( 64 - bk );
        }
    }

    private int peek( int n )
    {
        return (int) ( bb >>> ( 64 - n ) );
    }

    private void dump( int n )
    {
        bb <<= n;
        bk -= n;
    }

    /* Read and return `n' bits from the input stream. `n' must be <= 32. */
    private int get( int n )
        throws StreamFormatException, IOException
    {
        need( n );
        int x = peek( n );
        dump( n );
        return x;
    }

    /* Decode a single prefix code. The algorithm used is naive and slow. */
    private short get_sym()
        throws StreamFormatException, IOException
    {
        need( MAX_CODE_LENGTH );
        int x = pd.start[peek( HUFF_START_WIDTH )];
        int k = x & 0x1F;
        short s;

        if ( k <= HUFF_START_WIDTH )
        {
            /* Use look-up table in average case. */
            s = (short) ( x >> 5 );
        }
        else
        {
            /*
             * Code length exceeds HUFF_START_WIDTH, use canonical prefix decoding algorithm instead of look-up table.
             */
            while ( uge( bb, pd.base[k + 1] ) )
                k++;
            s = pd.perm[pd.count[k] + (int) ( ( bb - pd.base[k] ) >>> ( 64 - k ) )];
        }

        dump( k );
        return s;
    }

    /* Retrieve bitmap. */
    private void bmp()
        throws StreamFormatException, IOException
    {
        int i, j;
        short b = (short) get( 16 );
        as = 0;
        mtf.initialize();
        for ( i = 0; i < 16; i++ )
        {
            if ( b < 0 )
            {
                short s = (short) get( 16 );
                for ( j = 0; j < 16; j++ )
                {
                    if ( s < 0 )
                        mtf.imtf_slide[CMAP_BASE + as++] = (byte) ( 16 * i + j );
                    s *= 2;
                }
            }
            b *= 2;
        }
        as += 2;
    }

    /* Retrieve selector MTF values. */
    private void smtf()
        throws StreamFormatException, IOException
    {
        int g;
        for ( g = 0; g < ns; g++ )
        {
            sel[g] = 0;
            while ( sel[g] < nt && get( 1 ) != 0 )
                sel[g]++;
            if ( sel[g] == nt )
                bad();
        }
        if ( ns > 18001 )
            ns = 18001;
    }

    /* Retrieve code lengths. */
    private void trees()
        throws StreamFormatException, IOException
    {
        int t, s;
        for ( t = 0; t < nt; t++ )
        {
            len[t][0] = (byte) get( 5 );
            for ( s = 0; s < as; s++ )
            {
                if ( len[t][s] < 1 || len[t][s] > 20 )
                    bad();
                while ( get( 1 ) != 0 )
                {
                    len[t][s] += 1 - 2 * get( 1 );
                    if ( len[t][s] < 1 || len[t][s] > 20 )
                        bad();
                }
                len[t][s + 1] = len[t][s];
            }
        }
    }

    /* Retrieve block MTF values. */
    private void data()
        throws StreamFormatException, IOException
    {
        int g, i, t;
        int[] m = new int[6];
        for ( i = 0; i < 6; i++ )
            m[i] = i;
        nm = 0;
        for ( g = 0; g < ns; g++ )
        {
            i = sel[g];
            t = m[i];
            while ( i-- > 0 )
                m[i + 1] = m[i];
            m[0] = t;
            pd.make_tree( len[t], as );
            for ( i = 0; i < 50; i++ )
                if ( ( mv[nm++] = get_sym() ) == EOB )
                    return;
        }
        bad();
    }

    /* Retrieve block. */
    private void retr()
        throws StreamFormatException, IOException
    {
        rnd = get( 1 ) != 0;
        idx = get( 24 );
        bmp();
        nt = get( 3 );
        if ( nt < 2 || nt > 6 )
            bad();
        ns = get( 15 );
        smtf();
        trees();
        data();
    }

    /* Apply IMTF transformation. */
    private void imtf()
        throws StreamFormatException
    {
        int i, s, r, h, c;
        bs = r = h = 0;
        c = mtf.imtf_slide[mtf.imtf_row[0]] & 0xFF;
        for ( i = 0; i < nm; i++ )
        {
            s = mv[i];
            if ( s >= RUN_A )
            {
                r += 1 << ( h + s - RUN_A );
                h++;
                if ( r < 0 )
                    bad();
            }
            else
            {
                if ( bs + r > mbs )
                    bad();
                while ( r-- != 0 )
                    tt[bs++] = c;
                if ( s == EOB )
                    break;
                c = mtf.mtf_one( s );
                h = 0;
                r = 1;
            }
        }
    }

    /* Apply IBWT transformation. */
    private void ibwt()
        throws StreamFormatException
    {
        int i, c;
        int[] f = new int[256];
        if ( idx >= bs )
            bad();
        for ( i = 0; i < 256; i++ )
            f[i] = 0;
        for ( i = 0; i < bs; i++ )
            f[tt[i]]++;
        for ( i = c = 0; i < 256; i++ )
            f[i] = ( c += f[i] ) - f[i];
        for ( i = 0; i < bs; i++ )
            tt[f[tt[i] & 0xFF]++] |= i << 8;
        idx = tt[idx];
        for ( i = 0; i < bs; i++ )
        {
            idx = tt[idx >> 8];
            blk[i] = (byte) idx;
        }
    }

    /* Derandomize block if it's randomized. */
    private void derand()
    {
        int i = 0, j = 617;
        while ( rnd && j < bs )
        {
            blk[j] ^= 1;
            i = ( i + 1 ) & 0x1FF;
            j += rand_table[i];
        }
    }

    /* Emit block. RLE is undone here. */
    private void emit()
        throws StreamFormatException, IOException
    {
        int i, r, c, d;
        r = 0;
        c = -1;
        for ( i = 0; i < bs; i++ )
        {
            d = c;
            c = blk[i] & 0xFF;
            crc = ( ( crc << 8 ) & 0xFFFFFFFF ) ^ crc_table[( crc >>> 24 ) ^ c];
            write( c );
            if ( c != d )
                r = 1;
            else
            {
                r++;
                if ( r >= 4 )
                {
                    int j;
                    if ( ++i == bs )
                        bad();
                    for ( j = 0; j < ( blk[i] & 0xFF ); j++ )
                    {
                        crc = ( ( crc << 8 ) & 0xFFFFFFFF ) ^ crc_table[( crc >>> 24 ) ^ c];
                        write( c );
                    }
                    r = 0;
                }
            }
        }
    }

    /* Parse stream and bock headers, decompress any blocks found. */
    public void expand()
        throws StreamFormatException, IOException
    {
        int t = 0, c;
        if ( get( 24 ) != 0x425A68 )
            bad();
        t = get( 8 ) - 0x31;
        if ( t >= 9 )
            bad();
        do
        {
            c = 0;
            mbs = 100000 * ( t + 1 );
            while ( ( t = get( 16 ) ) == 0x3141 )
            {
                if ( get( 32 ) != 0x59265359 )
                    bad();
                t = get( 32 );
                retr();
                imtf();
                ibwt();
                derand();
                crc = 0xFFFFFFFF;
                emit();
                if ( ( crc ^ 0xFFFFFFFF ) != t )
                    bad();
                c = ( ( c << 1 ) & 0xFFFFFFFF ) ^ ( c >>> 31 ) ^ t;
            }
            if ( t != 0x1772 )
                bad();
            if ( get( 32 ) != 0x45385090 )
                bad();
            if ( get( 32 ) != c )
                bad();
            bk = 0;
        }
        while ( read() == 0x42 && read() == 0x5A && read() == 0x68 && ( t = get( 8 ) - 0x31 ) < 9 );
    }

    public static void main( String[] args )
    {
        try
        {
            MBC mbc = new MBC( System.in, System.out );
            mbc.expand();
        }
        catch ( StreamFormatException e )
        {
            System.err.println( "Data error" );
            System.exit( 1 );
        }<commit_msg>Use faster decoder and emitter<commit_after>/*-
 * Copyright (c) 2014 <NAME>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this 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.
 */
package org.lbzip2.impl;

import static org.lbzip2.impl.Constants.MAX_CODE_LENGTH;
import static org.lbzip2.impl.MtfDecoder.CMAP_BASE;
import static org.lbzip2.impl.PrefixDecoder.EOB;
import static org.lbzip2.impl.PrefixDecoder.HUFF_START_WIDTH;
import static org.lbzip2.impl.PrefixDecoder.RUN_A;
import static org.lbzip2.impl.Status.OK;
import static org.lbzip2.impl.Unsigned.uge;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;

import org.lbzip2.StreamFormatException;

public class MBC
{
    private final InputStream in;

    private final OutputStream out;

    public MBC( InputStream in, OutputStream out )
    {
        this.in = in;
        this.out = out;
    }

    private static void err( String msg )
        throws StreamFormatException
    {
        throw new StreamFormatException( msg );
    }

    /* Read a single byte from stdin. */
    private int read()
        throws IOException
    {
        return in.read();
    }

    /* Print an error message and terminate. */
    private static void bad()
        throws StreamFormatException
    {
        err( "Data error" );
    }

    private long bb; /* the bit-buffer (left-justified) */

    private int bk; /* number of bits remaining in the `bb' bit-buffer */

    private int mbs; /* maximal block size (100k-900k in 100k steps) */

    private final Decoder ds = new Decoder();

    private int as; /*
                     * alphabet size (number of distinct prefix codes, 3-258)
                     */

    private int nt; /*
                     * number of prefix trees used for current block (2-6)
                     */

    private int ns; /* number of selectors (1-32767) */

    private int nm; /* number of MTF values */

    private final byte[][] len = new byte[6][259]; /*
                                                    * code lengths for different trees (element 258 is a sentinel)
                                                    */

    private final byte[] sel = new byte[32767]; /* selector MTF values */

    private final MtfDecoder mtf = new MtfDecoder();

    private final PrefixDecoder pd = new PrefixDecoder();

    private final short[] mv = new short[900050]; /*
                                                   * MTF values (elements 900000-900049 are sentinels)
                                                   */

    private void need( int n )
        throws StreamFormatException, IOException
    {
        while ( bk < n )
        {
            long c = in.read();
            if ( c < 0 )
                bad();
            bk += 8;
            bb += c << ( 64 - bk );
        }
    }

    private int peek( int n )
    {
        return (int) ( bb >>> ( 64 - n ) );
    }

    private void dump( int n )
    {
        bb <<= n;
        bk -= n;
    }

    /* Read and return `n' bits from the input stream. `n' must be <= 32. */
    private int get( int n )
        throws StreamFormatException, IOException
    {
        need( n );
        int x = peek( n );
        dump( n );
        return x;
    }

    /* Decode a single prefix code. The algorithm used is naive and slow. */
    private short get_sym()
        throws StreamFormatException, IOException
    {
        need( MAX_CODE_LENGTH );
        int x = pd.start[peek( HUFF_START_WIDTH )];
        int k = x & 0x1F;
        short s;

        if ( k <= HUFF_START_WIDTH )
        {
            /* Use look-up table in average case. */
            s = (short) ( x >> 5 );
        }
        else
        {
            /*
             * Code length exceeds HUFF_START_WIDTH, use canonical prefix decoding algorithm instead of look-up table.
             */
            while ( uge( bb, pd.base[k + 1] ) )
                k++;
            s = pd.perm[pd.count[k] + (int) ( ( bb - pd.base[k] ) >>> ( 64 - k ) )];
        }

        dump( k );
        return s;
    }

    /* Retrieve bitmap. */
    private void bmp()
        throws StreamFormatException, IOException
    {
        int i, j;
        short b = (short) get( 16 );
        as = 0;
        mtf.initialize();
        for ( i = 0; i < 16; i++ )
        {
            if ( b < 0 )
            {
                short s = (short) get( 16 );
                for ( j = 0; j < 16; j++ )
                {
                    if ( s < 0 )
                        mtf.imtf_slide[CMAP_BASE + as++] = (byte) ( 16 * i + j );
                    s *= 2;
                }
            }
            b *= 2;
        }
        as += 2;
    }

    /* Retrieve selector MTF values. */
    private void smtf()
        throws StreamFormatException, IOException
    {
        int g;
        for ( g = 0; g < ns; g++ )
        {
            sel[g] = 0;
            while ( sel[g] < nt && get( 1 ) != 0 )
                sel[g]++;
            if ( sel[g] == nt )
                bad();
        }
        if ( ns > 18001 )
            ns = 18001;
    }

    /* Retrieve code lengths. */
    private void trees()
        throws StreamFormatException, IOException
    {
        int t, s;
        for ( t = 0; t < nt; t++ )
        {
            len[t][0] = (byte) get( 5 );
            for ( s = 0; s < as; s++ )
            {
                if ( len[t][s] < 1 || len[t][s] > 20 )
                    bad();
                while ( get( 1 ) != 0 )
                {
                    len[t][s] += 1 - 2 * get( 1 );
                    if ( len[t][s] < 1 || len[t][s] > 20 )
                        bad();
                }
                len[t][s + 1] = len[t][s];
            }
        }
    }

    /* Retrieve block MTF values. */
    private void data()
        throws StreamFormatException, IOException
    {
        int g, i, t;
        int[] m = new int[6];
        for ( i = 0; i < 6; i++ )
            m[i] = i;
        nm = 0;
        for ( g = 0; g < ns; g++ )
        {
            i = sel[g];
            t = m[i];
            while ( i-- > 0 )
                m[i + 1] = m[i];
            m[0] = t;
            pd.make_tree( len[t], as );
            for ( i = 0; i < 50; i++ )
                if ( ( mv[nm++] = get_sym() ) == EOB )
                    return;
        }
        bad();
    }

    /* Retrieve block. */
    private void retr()
        throws StreamFormatException, IOException
    {
        ds.rand = get( 1 ) != 0;
        ds.bwt_idx = get( 24 );
        bmp();
        nt = get( 3 );
        if ( nt < 2 || nt > 6 )
            bad();
        ns = get( 15 );
        smtf();
        trees();
        data();
    }

    /* Apply IMTF transformation. */
    private void imtf()
        throws StreamFormatException
    {
        int i, s, r, h, c;
        ds.block_size = r = h = 0;
        c = mtf.imtf_slide[mtf.imtf_row[0]] & 0xFF;
        for ( i = 0; i < nm; i++ )
        {
            s = mv[i];
            if ( s >= RUN_A )
            {
                r += 1 << ( h + s - RUN_A );
                h++;
                if ( r < 0 )
                    bad();
            }
            else
            {
                if ( ds.block_size + r > mbs )
                    bad();
                while ( r-- != 0 )
                    ds.tt[ds.block_size++] = c;
                if ( s == EOB )
                    break;
                c = mtf.mtf_one( s );
                h = 0;
                r = 1;
            }
        }
    }

    private void decode_and_emit()
        throws StreamFormatException, IOException
    {
        if ( ds.bwt_idx >= ds.block_size )
            bad();
        Arrays.fill( ds.ftab, 0 );
        for ( int i = 0; i < ds.block_size; i++ )
            ds.ftab[ds.tt[i]]++;

        ds.decode();

        byte[] buf = new byte[50000000];
        int[] len = new int[1];
        len[0] = buf.length;
        Status status = ds.emit( buf, 0, len );
        assert ( status == OK );
        out.write( buf, 0, buf.length - len[0] );
    }

    /* Parse stream and bock headers, decompress any blocks found. */
    public void expand()
        throws StreamFormatException, IOException
    {
        int t = 0, c;
        if ( get( 24 ) != 0x425A68 )
            bad();
        t = get( 8 ) - 0x31;
        if ( t >= 9 )
            bad();
        do
        {
            c = 0;
            mbs = 100000 * ( t + 1 );
            while ( ( t = get( 16 ) ) == 0x3141 )
            {
                if ( get( 32 ) != 0x59265359 )
                    bad();
                t = get( 32 );
                retr();
                imtf();
                decode_and_emit();
                if ( ds.crc != t )
                    bad();
                c = ( ( c << 1 ) & 0xFFFFFFFF ) ^ ( c >>> 31 ) ^ t;
            }
            if ( t != 0x1772 )
                bad();
            if ( get( 32 ) != 0x45385090 )
                bad();
            if ( get( 32 ) != c )
                bad();
            bk = 0;
        }
        while ( read() == 0x42 && read() == 0x5A && read() == 0x68 && ( t = get( 8 ) - 0x31 ) < 9 );
    }

    public static void main( String[] args )
    {
        try
        {
            MBC mbc = new MBC( System.in, System.out );
            mbc.expand();
        }
        catch ( StreamFormatException e )
        {
            System.err.println( "Data error" );
            System.exit( 1 );
        }
{'fraction_non_alphanumeric': 0.12381128243006186, 'fraction_numerical': 0.026174868433200996, 'mean_word_length': 1.1408241921138453, 'pattern_counts': {'":': 0, '<': 78, '<?xml version=': 0, '>': 54, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 7, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2124032', 'n_tokens_mistral': 7036, 'n_tokens_neox': 6313, 'n_words': 2001}