Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

__int128 constant or operators problems

2013-01-11
2013-06-06
  • Hello,
    I tested the following 2 compress/decompress source code files with "tdm64-gcc-4.7.1-3.exe" and "CodeBlock 10.5".
    The main aim of these source files is to test the possibility to go below the Hutter Prize Limit of 15932968 of enwik8 file.
    The main input for the compress program is the "archive8.dat" file of 15932968 bytes, renamed into "in.txt".

    I wanted to test these source codes with __int128 type instead __int64.
    I modified all constants, numbers and indexes accordingly to 128 bits in the code but I obtain invalid decompress data even I add only one "F" to the hexa constants and modify the indexes accordingly.

    I want to ask you how you suggest to proceed to use correctly the constants and __int128 type?

    Is there an inside error specific to __int128 type? because after compression the file became smaller if only one "F" is added to the constants.
    Should it be used the __int128 constants and operators in an other way?
    It is hard to belive that the file 15932968 can be compressed again.

    Thank you very much for the attention,
    Best regards,
    Adrian,

    # include "conio.h"
    # include "stdio.h"
    # include "string.h"
    # include "stdlib.h"

    # define MAXVALUE (0x7FFFFFFFFFFFFFFF)

    typedef unsigned /*long int*/ __int64 UL_int;

    FILE * pf,* rez_aux, * rez, *rez_huf;

    UL_int NOMINATOR=1, DENOMINATOR=1;
    UL_int ch_afis = 0;
    UL_int in_size;
    UL_int nCHAR_read = 0;
    UL_int tc_length = 0;
    UL_int number_ch_written = 0;

    signed long c = -1;
    long GAIN = 0;

    int ct8 = 0;
    int i = 0;
    int rb;
    int tcc = 1;
    int tpc = 1;
    int write_char = 0;
    int write_char_huf = 0;
    int ch_read;//The ASCII code of the character

    char bin_asc;
    char sir_length;
    char FRAGMENT_CHAR;
    char write_contor = 0;
    char write_contor_huf = 0;

    int last_bit = 0;
    UL_int old_N, old_D;
    char rest;

    void Write_In_File(char * sir)
    {
    UL_int k_var;
    UL_int length = 0;

    length = strlen(sir);

    for(k_var=0;k_var<length;k_var++)
    {

    write_char = write_char * 2;

    if(sir == '1')
    {
    write_char = write_char + 1;
    }

    write_contor++;

    if((write_contor>0)&&((write_contor % 8)==0))
    {
    fputc(write_char,rez);

    write_contor = 0;
    write_char = 0;

    number_ch_written ++;
    }

    }

    }

    void Write_In_File_rest(char * sir)
    {
    UL_int k_var;
    UL_int length = 0;

    write_char = 0;
    length = strlen(sir);

    for(k_var=0;k_var<length;k_var++)
    {

    write_char = write_char * 2;

    if(sir == '1')
    {
    write_char = write_char + 1;
    }

    write_contor++;

    }

    write_char /= 2;

    fputc(write_char,rez);

    write_contor = 0;
    write_char = 0;

    number_ch_written ++;

    }

    void Write_In_File_huf(char * sir)
    {
    UL_int k_var;
    UL_int length = 0;

    length = strlen(sir);

    for(k_var=0;k_var<length;k_var++)
    {

    write_char_huf = write_char_huf * 2;

    if(sir == '1')
    {
    write_char_huf = write_char_huf + 1;
    }

    write_contor_huf++;

    if((write_contor_huf>0)&&((write_contor_huf % 8)==0))
    {
    fputc(write_char_huf,rez_huf);

    write_contor_huf = 0;
    write_char_huf = 0;

    number_ch_written ++;
    }

    }

    }

    void write_progress()
    {
    ch_afis ++;

    if( (ch_afis % 1000 ) == 0 )
    {
    printf("\b");

    switch( (ch_afis / 1000) % 4)
    {
    case 0: printf("-"); break;
    case 1: printf("\\"); break;
    case 2: printf("|"); break;
    case 3: printf("/"); break;
    }

    printf("%7.3f\%%",(((double)nCHAR_read/in_size)*100));
    printf("\b\b\b\b\b\b\b\b");
    }
    }

    void Write_Original_Bits()
    {
    fprintf(rez_aux,"#0 LENGTH = %28lu", tc_length);
    fprintf(rez_aux," GAIN = %10ld",GAIN);
    fprintf(rez_aux," TOTAL = %10lu\n",8*in_size);

    Write_In_File(FRAGMENT_CHAR);
    }

    void Write_Fractions(UL_int NOM, UL_int DENOM)
    {
    int k;
    int b=0;

    //Write the "bookmark"
    Write_In_File("1");

    if(NOM<MAXVALUE)
    {
    Write_In_File("0");
    Write_In_File("0");

    b=1;
    }
    if(DENOM<MAXVALUE)
    {
    Write_In_File("0");
    Write_In_File("1");

    b=2;
    }

    if((NOM>MAXVALUE)&&(DENOM>MAXVALUE))
    {
    Write_In_File("1");
    }

    if(b==1)
    NOM = NOM + MAXVALUE+1;
    else if(b==2)
    DENOM = DENOM + MAXVALUE+1;

    for(k=62;k>=0;k-)
    if( (NOM>>k & 1) == 1 )
    Write_In_File("1");
    else if( (NOM>>k & 1) == 0 )
    Write_In_File("0");

    for(k=62;k>=0;k-)
    if( (DENOM>>k & 1) == 1 )
    Write_In_File("1");
    else if( (DENOM>>k & 1) == 0 )
    Write_In_File("0");

        /*
    for(k=63;k>=0;k-)
    if( (NOM>>k & 1) == 1 )
    Write_In_File("1");
    else if( (NOM>>k & 1) == 0 )
    Write_In_File("0");

    for(k=63;k>=0;k-)
    if( (DENOM>>k & 1) == 1 )
    Write_In_File("1");
    else if( (DENOM>>k & 1) == 0 )
    Write_In_File("0");
    */

    }

    /*-----------------------------------------------*/
    /* Function for the generating the "Calkin-Wilf" tree of "c" level */
    /*-----------------------------------------------*/
    int CW_tree()
    {
    Again:;

    c = c+1;

    if( !feof(pf) )
    {

    //The NOMINATOR or DENOMINATOR has 32 bits
    if( (0xFFFFFFFFFFFFFFFF-NOMINATOR<DENOMINATOR )||(0xFFFFFFFFFFFFFFFF-DENOMINATOR<NOMINATOR ) )
    //if( (NOMINATOR>MAXVALUE )||( DENOMINATOR>MAXVALUE) )
    {
    //The fractions should be written in the file
    if( c > 128 )
    {
    tcc = 1;

    FRAGMENT_CHAR = '\0';

    Write_Fractions(NOMINATOR,DENOMINATOR);

    GAIN = GAIN + c - 65;

    fprintf(rez_aux,"#1 %10lu/%10lu",NOMINATOR,DENOMINATOR);
    fprintf(rez_aux," H_Tree = %5ld ",c);
    fprintf(rez_aux," GAIN = %10ld",GAIN);
    fprintf(rez_aux," TOTAL = %10lu\n",8*in_size);

    }
    //The ORIGINAL bits should be copied in the file
    else
    {
    tcc = 0;

    //Write the "bookmark"
    Write_In_File("0");

    tc_length = c;

    //Modify here the FRAGMENT_CHAR: shorter with "c" position
    FRAGMENT_CHAR = '\0';

    Write_Original_Bits();

    FRAGMENT_CHAR = '\0';

    }

    NOMINATOR = 1;
    DENOMINATOR = 1;
    c = 1;

    tpc = tcc;

    }
    //END of "The DENOMINATOR or DENOMINATOR has 32 bits"

    //******************************************************
    //should read a new character from the file
    if( ct8 == 0 )
    {
    ch_read=fgetc(pf);

    nCHAR_read ++;
    write_progress();

    for(int i=7;i>=0;i-)
    if(((ch_read&(1<<i)) >> i) == 1)
    bin_asc_ = '1';
    else if(((ch_read&(1<<i)) >> i) == 0)
    bin_asc = '0';

    bin_asc = '\0';
    }

    if(bin_asc == '0')
    {
    DENOMINATOR = NOMINATOR + DENOMINATOR;

    ct8 ++;
    ct8 = ct8 % 8;

    last_bit = 0;

    strcat(FRAGMENT_CHAR,"0");

    goto Again;
    }
    else if(bin_asc == '1')
    {
    NOMINATOR = NOMINATOR + DENOMINATOR;

    ct8 ++;
    ct8 = ct8 % 8;

    last_bit = 1;

    strcat(FRAGMENT_CHAR,"1");

    goto Again;
    }

    }// if( !feof(pf) )

    }

    int main(void)
    {

    printf(" CWT Compress: using the Calkin-Wilf Tree\n");
    printf("============ Author: BOCUT Adrian Sebastian ============\n");
    printf("\n");
    printf("Start…");

    //for(int st=0;st<1000; st++)
    //FRAGMENT_CHAR = '0';

    FRAGMENT_CHAR = '\0';

    pf = fopen("in.txt","rb");
    rez_aux = fopen("rez_aux.txt","wb");
    rez = fopen("rez.txt","wb");
    rez_huf = fopen("rez_huf.txt","wb");

    fseek(pf, 0L, SEEK_END);
    in_size = ftell(pf);
    fseek(pf, 0L, SEEK_SET);

    ct8 = 0;

    /* The root is treated separatly */
    NOMINATOR= 1;
    DENOMINATOR = 1;

    /* Generation of the CALKIN-WILF tree fractions */
    //This is the level of the current fraction in the tree
    c= -1;

    CW_tree();

    //Write the "bookmark"
    Write_In_File("0");
    Write_Original_Bits();

    write_char = 0;
        _itoa(write_char,rest,2);
    int al = 0;
    al = strlen(rest);
    for(int z=0; z<=8-al;z++)
    strncat(rest,"0",100);

        Write_In_File_rest(rest);

    fprintf(rez_aux,"#0 GAIN = %10ld",GAIN);
    fprintf(rez_aux," TOTAL = %10lu\n",8*in_size);
    fprintf(rez_aux,"\n\nNumber of read chars = %lu\n",nCHAR_read);
    fprintf(rez_aux,"\n\nNumber of written chars = %lu\n",number_ch_written);
    printf("\n\nNumber of saved bits = %ld\n",GAIN);
    printf("\n\nNumber of read chars = %lu\n",nCHAR_read);
    printf("\n\nNumber of written chars = %lu\n",number_ch_written);
    printf("\b\nEND…\n");

    fflush(rez);
    fclose(rez);
    fclose(rez_aux);
    fclose(rez_huf);
    fclose(pf);

    getche();

    return 1;
    }

    # include "stdio.h"
    # include "conio.h"
    # include "malloc.h"
    # include "stdlib.h"
    # include "io.h"

    # define MAXVALUE (0x7FFFFFFFFFFFFFFF)

    typedef unsigned /*long int*/ __int64 UL_int;

    FILE * file_in, * file_out;

    UL_int ch_write_progress = 0;
    UL_int nCHAR_read = 0;
    UL_int file_in_size;
    UL_int NOMINATOR = 0, DENOMINATOR = 0;

    UL_int x,y;
    int write_char = 0;
    int new_char = 0;

    unsigned char ch_read = 0;
    char bit = 0;
    char contor_read_bits = 0;

    typedef char * SIR;
    SIR array_fraction;

    char write_contor = 0;

    int first = 0;

    int contorBitiScriere = 0;
    int buffer=0;

    UL_int LUNGIME = 0;

    int orig_array = 0;
    UL_int length = 0;

    UL_int l = 0;
    UL_int NOM, DENOM;

    void write_byte_sequence();
    void write_byte_sequence_from_fraction();

    void ScrieBIT(int bit)
    {
    buffer <<= 1;
    buffer |= (bit & 0x0001);
    contorBitiScriere++;
    if(contorBitiScriere%8==0)
    {
    fprintf(file_out,"%c",buffer);
    fflush(file_out);
    buffer = 0;
    contorBitiScriere = 0;
    }
    }

    void strreverse(UL_int LUNG)
    {
    UL_int i;
    char aux;

    for(i=0;i<(LUNG / 2.0);i++)
    {
    aux = array_fraction;
    array_fraction = array_fraction;
    array_fraction = aux;
    }
    }

    /**********************************************************/
    void Write_In_File(UL_int LUNG)
    {

    UL_int i,j;

    length = LUNG;

    for(i=0;i<length;i++)
    {

    write_char = write_char * 2;
    if(array_fraction == '1')
    write_char = write_char + 1;

    write_contor ++;
    if((write_contor % 8) == 0)
    {
    write_contor = 0;

    new_char = 0;
    for(j=0;j<8;j++)
    {
    new_char = new_char * 2;

    if((write_char % 2) == 1)
    {
    new_char = new_char + 1;
    ScrieBIT(1);
    }
    else
    ScrieBIT(0);

    write_char /= 2;
    }
    }
    }

    }

    void read_from_file();

    void write_progress()
    {
    ch_write_progress ++;

    if( (ch_write_progress % 2 ) == 0 )
    {
    printf("\b");

    switch( (ch_write_progress / 1000) % 4)
    {
    case 0: printf("-"); break;
    case 1: printf("\\"); break;
    case 2: printf("|"); break;
    case 3: printf("/"); break;
    }

    printf("%7.3f\%%",(((long double)nCHAR_read/(long double)file_in_size)*100));
    printf("\b\b\b\b\b\b\b\b");

    }
    }

    char read_one_bit_from_file()
    {
    char b = 0;

    //Test if a new character should be read from the file
    if(contor_read_bits == 0)
    {
    if((((nCHAR_read) <= file_in_size)))
    ch_read = fgetc(file_in);

    nCHAR_read ++;
    write_progress();
    }

    //Provide the current bit
    b = (ch_read & (1<<(7-contor_read_bits))) >> (7-contor_read_bits);

    ++contor_read_bits ;
    contor_read_bits = contor_read_bits % 8;

    return b;
    }

    void write_byte_sequence()
    {

    UL_int length;
    UL_int k;
    char i,b;

    NOM = 1;
    DENOM = 1;
    l = 1;

    while( (0xFFFFFFFFFFFFFFFF-NOM>=DENOM )&&(0xFFFFFFFFFFFFFFFF-DENOM>=NOM ) && (((nCHAR_read) <= file_in_size)))
    {
    b = read_one_bit_from_file();
    l ++;

    if(!feof(file_in))
    {
    if(b == 1)
    {
    array_fraction = '1';
    Write_In_File(1);

    NOM = NOM + DENOM;
    }
    else
    {
    array_fraction = '0';
    Write_In_File(1);

    DENOM = NOM + DENOM;
    }
    }
    }
    }

    void write_byte_sequence_from_fraction()
    {

    UL_int valid_length = 0;
    long double magnitude = 0.0;
    char i,b,b1,b2, j;
    UL_int VAL = 0;

    NOMINATOR = 0;
    DENOMINATOR = 0;

    b1 = read_one_bit_from_file();
    if(b1==0)
    b2 = read_one_bit_from_file();

    //Read 32 bits for NOMINATOR
    for(i=62;i>=0;i-)
    {
    VAL = 1;
    for(j=0;j<i;j++)
    VAL = VAL * 2;

    b = read_one_bit_from_file();
    if(b == 1)
    NOMINATOR = NOMINATOR + VAL;
    }

    //Read 32 bits for NOMINATOR
    for(i=62;i>=0;i-)
    {
    VAL = 1;
    for(j=0;j<i;j++)
    VAL = VAL * 2;

    b = read_one_bit_from_file();
    if(b == 1)
    DENOMINATOR = DENOMINATOR + VAL;
    }

    NOMINATOR = NOMINATOR + MAXVALUE+1;
    DENOMINATOR = DENOMINATOR + MAXVALUE+1;

    if((b1==0)&&(b2==0))
    NOMINATOR = NOMINATOR - (MAXVALUE+1);
    if((b1==0)&&(b2==1))
    DENOMINATOR = DENOMINATOR - (MAXVALUE+1);

    x = NOMINATOR;
    y = DENOMINATOR;

    array_fraction = '\0';

    while(x!=y)
    {
    magnitude = (long double)x / (long double)y;

    if( magnitude >= 1.0 )
    {
    x = x - y;
    array_fraction='1';
    }
    else if( magnitude < 1.0 )
    {
    y = y - x;
    array_fraction='0';
    }

    valid_length ++;

    }

    array_fraction = '\0';

    strreverse(valid_length);

    Write_In_File(valid_length);

    orig_array = 0;

    }

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    void read_from_file()
    {
    while((((nCHAR_read) <= file_in_size)))
    {

    bit = read_one_bit_from_file();

    if(bit == 0)
    {
    write_byte_sequence();
    }

    else

    {

    write_byte_sequence_from_fraction();

    }

    }

    }

    /**********************************************************/

    int main(void)
    {
    array_fraction = (SIR)malloc(1000000*sizeof(char));

    file_in = fopen("rez.txt","rb");
    file_out = fopen("decompressed.txt","wb");
    //fseek(file_in, 0L, SEEK_END);
    //file_in_size = ftell(file_in);
    //fseek(file_in, 0L, SEEK_SET);

    file_in_size = _filelength(_fileno(file_in));

    printf(" CWT DEcompress: using the Calkin-Wilf Tree\n");
    printf("============ Author: BOCUT Adrian Sebastian ============\n");
    printf("\n");
    printf("Start…");

    read_from_file();

    fflush(file_out);
    fclose(file_in);
    fclose(file_out);

    printf("END…");
    getche();

    return 1;

    }
    _

     
  • Kai Tietz
    Kai Tietz
    2013-01-12

    The gcc compiler doesn't provide a way to express directly constant 128-bit integer-scalar values.  Nevertheless you can achieve that with following helper-macros:

    /* unsigned __int128 typed constant. */
    #define __C_UINT128(LOW, HIGH) ((((unsigned __int128) (HIGH)) << 32) | ((unsigned __int128) (LOW)))
    /* signed __int128 typed constant. */
    #define __C_INT128(LOW, HIGH) (signed __int128) (__C_UINT128(LOW, HIGH))

    So the MAX_INT for 128-bit is __C_INT128(0xfffffffffffffffull,0x7fffffffffffffffull).

    Hopes that helps you,

    Kai