swish-e/src/compress.c

/*
** Copyright (C) 1995, 1996, 1997, 1998 Hewlett-Packard Company
** Originally by Kevin Hughes, kev@kevcom.com, 3/11/94
**
** This program and library is free software; you can redistribute it and/or
** modify it under the terms of the GNU (Library) General Public License
** as published by the Free Software Foundation; either version 2
** of the License, or any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU (Library) General Public License for more details.
**
** You should have received a copy of the GNU (Library) General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
**
** 2001-02-12 rasc   errormsg "print" changed...
**
*/

#include "swish.h"
#include "string.h"
#include "compress.h"
#include "mem.h"
#include "error.h"
#include "merge.h"
#include "docprop.h"
#include "index.h"
#include "search.h"
#include "hash.h"
#include "ramdisk.h"
#include "swish_qsort.h"
#include "file.h"


/* 2001-05 jmruiz */
/* Routines for compressing numbers - Macros converted to routines */

/* Compress a number and writes it to a file */
void    compress1(int num, FILE * fp, int (*f_putc) (int, FILE *))
{
    int     _i = 0,
            _r = num;
    unsigned char _s[MAXINTCOMPSIZE];

    /* Trivial case: 0 */
    if(!_r)
    {
        f_putc(0,fp);
        return;
    }

    /* Any other case ... */
    while (_r)
    {
        _s[_i++] = _r & 127;
        _r >>= 7;
    }
    while (--_i >= 0)
        f_putc(_s[_i] | (_i ? 128 : 0), fp);
}

/* Compress a number and writes it to a buffer */
/* buffer must be previously allocated */
/* returns the decreased buffer pointer after storing the compressed number in it */
unsigned char *SW_compress2(int num, unsigned char *buffer)
{
    int     _i = num;

    /* Trivial case: 0 */
    if(!_i)
    {
        *buffer-- = 0; 
        return 0;
    }

    /* Any other case ... */
    while (_i)
    {
        *buffer = _i & 127;
        if (_i != num)
            *buffer |= 128;
        _i >>= 7;
        buffer--;
    }

    return buffer;
}

/* Compress a number and writes it to a buffer */
/* buffer must be previously allocated */
/* returns the incrmented buffer pointer after storing the compressed number in it */
unsigned char *compress3(int num, unsigned char *buffer)
{
    int     _i = 0,
            _r = num;
    unsigned char _s[MAXINTCOMPSIZE];

    /* Trivial case: 0 */
    if(!_r)
    {
        *buffer++ = 0;
        return buffer;
    }

    /* Any other case ... */
    while (_r)
    {
        _s[_i++] = _r & 127;
        _r >>= 7;
    }
    while (--_i >= 0)
        *buffer++ = (_s[_i] | (_i ? 128 : 0));

    return buffer;
}

/* Uncompress a number from a file */
int     uncompress1(FILE * fp, int (*f_getc) (FILE *))
{
    int     _c;
    int     num = 0;

    do
    {
        _c = (int) f_getc(fp);
        num <<= 7;
        num |= _c & 127;
        if (!num)
            break;
    }
    while (_c & 128);

    return num;
}

/* same routine but this works with a memory forward buffer instead of file */
/* it also increases the buffer pointer */
int     uncompress2(unsigned char **buffer)
{
    int     _c;
    int     num = 0;
    unsigned char *p = *buffer;

    do
    {
        _c = (int) ((unsigned char) *p++);
        num <<= 7;
        num |= _c & 127;
        if (!num)
            break;
    }
    while (_c & 128);

    *buffer = p;
    return num;
}

/* Rourtines to make long integers portable */
unsigned long PACKLONG(unsigned long num)
{
    unsigned long _i = 0L;
    unsigned char *_s;

    if (num)
    {
        _s = (unsigned char *) &_i;
        _s[0] = (unsigned char) ((num >> 24) & 0xFF);
        _s[1] = (unsigned char) ((num >> 16) & 0xFF);
        _s[2] = (unsigned char) ((num >> 8) & 0xFF);
        _s[3] = (unsigned char) (num & 0xFF);
        return _i;
    }
    return num;
}

/* Same routine - Packs long in buffer */
void    PACKLONG2(unsigned long num, unsigned char *buffer)
{
    buffer[0] = (unsigned char) ((num >> 24) & 0xFF);
    buffer[1] = (unsigned char) ((num >> 16) & 0xFF);
    buffer[2] = (unsigned char) ((num >> 8) & 0xFF);
    buffer[3] = (unsigned char) (num & 0xFF);
}


unsigned long UNPACKLONG(unsigned long num)
{
    unsigned char *_s = (unsigned char *) &num;

    return (_s[0] << 24) + (_s[1] << 16) + (_s[2] << 8) + _s[3];
}

/* Same macro - UnPacks long from buffer */
unsigned long UNPACKLONG2(unsigned char *buffer)
{
    return (buffer[0] << 24) + (buffer[1] << 16) + (buffer[2] << 8) + buffer[3];
}


/***********************************************************************************
*   09/00 Jose Ruiz 
*   Function to compress location data in memory 
*
*   Compresses a LOCATION entry
*
*   A single position LOCATION goes from 20 to 3 bytes.
*   three positions goes from 28 to 5.
* 
************************************************************************************/

#define IS_FLAG              0x80  /* Binary 10000000 */   
#define COMMON_STRUCTURE     0x60  /* Binary 01100000 */
#define COMMON_IN_FILE       0x20  /* Binary 00100000 */
#define COMMON_IN_HTML_BODY  0x40  /* Binary 01000000 */
#define POS_4_BIT            0x10  /* Binary 00010000 */
/************************************************************************

From Jose on Feb 13, 2002

IS_FLAG is to indicate that the byte is a flag. As far as I remember, I 
needed it to avoid null values.

When COMMON_STRUCTURE is on, this means that all the positions
have the same structure value. This helps a lot with non html
files and can save a lot of space.

When FREQ_AND_POS_EQ_1 is on, this means that freq is 1 and
pos[0]=1. Mmm, I am not sure if this is very useful now. Let me
explain better. This was useful for xml files with fields that contains
just one value. For example:
<code>00001</code>
<date>20001231</date>
But, now, I am not sure if this is useful because long time ago I
changed the position counter to not be reseted after a each field
change.
I need to check this.

POS_4_BIT indicates that all positions are within 16 positions
of each other and can thus be stored as 2 per byte.  Position numbers are
stored as a delta from the previous position.

Here's indexing /usr/doc:


23840 files indexed.  177638538 total bytes.  19739102 total words.
Elapsed time: 00:04:42 CPU time: 00:03:09
Indexing done!
      4 bit = 843,081 (total length = 10,630,425) 12 bytes/chunk
  not 4 bit = 13,052,904 (length 83,811,498) 6 bytes/chunk

I wonder if storing the initial postion would improve that much.


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


void compress_location_values(unsigned char **buf,unsigned char **flagp,int filenum,int frequency, int *posdata)
{
    unsigned char *p = *buf;
    unsigned char *flag;
    int structure = GET_STRUCTURE(posdata[0]);
    int common_structure = COMMON_STRUCTURE;
    int i;

    /* Make room for flag and init it */
    flag = p;
    *flagp = p;
    p++;

    *flag = IS_FLAG;

    /* Add file number */
    p = compress3(filenum, p);


    /* Check for special case frequency == 1 and position[0] < 128  && structure == IN_FILE */
    if(frequency == 1 && (GET_POSITION(posdata[0]) < 128) && structure == IN_FILE)
    {
        /* Remove IS_FLAG and store position in the lower 7 bits */
        /* In this way we have 0bbbbbbb in *flag 
        ** where bbbbbbb is the position and the leading 0 bit
        ** indicates that frequency is 1 and position is < 128 */
        *flag = (unsigned char) ((int)(GET_POSITION(posdata[0])));
    }
    else
    {
        /* Otherwise IS_FLAG is set */
        /* Now, let's see if all positions have the same structure to 
        ** get better compression */
        for(i=1;i<frequency;i++)
        {
            if(structure != GET_STRUCTURE(posdata[i]))
            {
                common_structure = 0;
                break;
            }
        }
        if(frequency < 16)
             (*flag) |= frequency; /* Store freequency in flag - low 4 bits */
        else                       
             p = compress3(frequency, p); /* Otherwise, leave frequency "as is" */
        /* Add structure if it is equal for all positions */
        if(common_structure)
        {
            switch(structure)
            {
                case IN_FILE:
                    *flag |= COMMON_IN_FILE; 
                     break;     

                case IN_BODY | IN_FILE:
                    *flag |= COMMON_IN_HTML_BODY; 
                     break;     

                default:         
                    *p++ = (unsigned char) structure;
                    *flag |= COMMON_STRUCTURE;
                    break;
            }
        }
    }
    *buf = p;
}

void compress_location_positions(unsigned char **buf,unsigned char *flag,int frequency, int *posdata)
{
    unsigned char *p = *buf;
    int i, j;

    if((*flag) & IS_FLAG)
    { 
        (*flag) |= POS_4_BIT;

        for(i = frequency - 1; i > 0 ; i--)
        {
            posdata[i] = SET_POSDATA(GET_POSITION(posdata[i]) - GET_POSITION(posdata[i-1]),GET_STRUCTURE(posdata[i]));
            if( GET_POSITION(posdata[i]) >= 16)
                (*flag) &= ~POS_4_BIT; 
        }

        /* Always write first position "as is" */
        p = compress3(GET_POSITION(posdata[0]), p);

        /* write the position data starting at 1 */
        if((*flag) & POS_4_BIT)
        {
            for (i = 1, j = 0; i < frequency ; i++, j++)
            {
                if(j % 2)
                    p[j/2] |= (unsigned char) GET_POSITION(posdata[i]);
                else
                    p[j/2] = (unsigned char) GET_POSITION(posdata[i]) << 4;
            }
            p += ((j + 1)/2);
        }
        else
        {
            for (i = 1; i < frequency; i++)
                p = compress3(GET_POSITION(posdata[i]), p);
        }

        /* Write out the structure bytes */
        if(! (*flag & COMMON_STRUCTURE))
            for(i = 0; i < frequency; i++)
                *p++ = (unsigned char) GET_STRUCTURE(posdata[i]);

        *buf = p;
    }
}

unsigned char *compress_location(SWISH * sw, IndexFILE * indexf, LOCATION * l)
{
    unsigned char *p,
           *q;
    int     i,
            max_size;
    unsigned char *flag;
    struct MOD_Index *idx = sw->Index;

    /* check if the work buffer is long enough */
    /* just to avoid bufferoverruns */
    /* In the worst case and integer will need MAXINTCOMPSIZE bytes */
    /* but fortunatelly this is very uncommon */

/* 2002/01 JMRUIZ
** Added an extra byte (MAXINTCOMPSIZE+1) for each position's structure
*/

    max_size = sizeof(unsigned char) + sizeof(LOCATION *) + (((sizeof(LOCATION) / sizeof(int) + 1) + (l->frequency - 1)) * (MAXINTCOMPSIZE + sizeof(unsigned char)));


    /* reallocate if needed */
    if (max_size > idx->len_compression_buffer)
    {
        idx->len_compression_buffer = max_size + 200;
        idx->compression_buffer = erealloc(idx->compression_buffer, idx->len_compression_buffer);
    }


    /* Pointer to the buffer */
    p = idx->compression_buffer;

    /* Add extra bytes for handling linked list */
//***JMRUIZ

    memcpy(p,&l->next,sizeof(LOCATION *));
    p += sizeof(LOCATION *);

    /* Add the metaID */
    p = compress3(l->metaID,p);

    compress_location_values(&p,&flag,l->filenum,l->frequency, l->posdata);
    compress_location_positions(&p,flag,l->frequency,l->posdata);


    /* Get the length of all the data */
    i = p - idx->compression_buffer;


    /* Did we underrun our buffer? */
    if (i > idx->len_compression_buffer)
        progerr("Internal error in compress_location routine");


    q = (unsigned char *) Mem_ZoneAlloc(idx->currentChunkLocZone, i);
    memcpy(q, idx->compression_buffer, i);

    return (unsigned char *) q;
}


void uncompress_location_values(unsigned char **buf,unsigned char *flag, int *filenum,int *frequency)
{
    unsigned char *p = *buf;

    *frequency = 0;

    *flag = *p++;

    if(!((*flag) & IS_FLAG))
    {
        *frequency = 1;
    }
    else
        (*frequency) |= (*flag) & 15;   /* Binary 00001111 */

    *filenum = uncompress2(&p);

    if(! (*frequency))
        *frequency = uncompress2(&p);

    *buf = p;
}

unsigned long four_bit_count = 0;
unsigned long four_bit_bytes = 0;
unsigned long not_four = 0;
unsigned long not_four_bytes = 0;
unsigned long four_bit_called = 0;
unsigned long not_four_called;


void uncompress_location_positions(unsigned char **buf, unsigned char flag, int frequency, int *posdata)
{
    int i, j, tmp;
    unsigned char *p = *buf;
    int common_structure = 0;
    int structure = 0;

    /* Check for special case frequency == 1 and position[0] < 128 and structure == IN_FILE */
    if (!(flag & IS_FLAG))
    {
        structure = IN_FILE;
        posdata[0] =  SET_POSDATA((int)(flag),structure);
    }
    else
    {
        /* Check for common structure */
        if ((tmp =(flag & COMMON_STRUCTURE)))
        {
            common_structure = COMMON_STRUCTURE;
            switch(tmp)
            {
                case COMMON_IN_FILE:
                    structure = IN_FILE;
                    break;

                case COMMON_IN_HTML_BODY:
                    structure = IN_FILE | IN_BODY;
                    break;

                default:
                    structure = (int)((unsigned char) *p++);
                    break;
            }
        }

        /* First position is always "as is" */
        posdata[0] = uncompress2(&p);

        /* Check if positions where stored as two values per byte or the old "compress" style */
        if(flag & POS_4_BIT)
        {
            for (i = 1, j = 0; i < frequency; i++, j++)
            {
                if(j%2)
                    posdata[i] = p[j/2] & 0x0F;
                else
                    posdata[i] = p[j/2] >> 4;
            }
            p += ((j + 1)/2);
        }
        else
        {
            for (i = 1; i < frequency; i++)
            {
                tmp = uncompress2(&p);
                posdata[i] = tmp;
            }
        }
        /* Position were compressed incrementally. So restore them */
        for(i = 1; i < frequency; i++)
            posdata[i] += posdata[i-1];

        /* Get structure */
        for(i = 0; i < frequency; i++)
        {
            if(!common_structure)
                structure = (int)((unsigned char) *p++);

            posdata[i] = SET_POSDATA(posdata[i],structure);
        }
    }
    /* Update buffer pointer */
    *buf = p;
}

/* 09/00 Jose Ruiz 
** Extract compressed location
*/
LOCATION *uncompress_location(SWISH * sw, IndexFILE * indexf, unsigned char *p)
{
    LOCATION *loc;
    int     metaID,
            filenum,
            frequency;
    unsigned char flag;

    metaID = uncompress2(&p);

    uncompress_location_values(&p,&flag,&filenum,&frequency);

    loc = (LOCATION *) emalloc(sizeof(LOCATION) + (frequency - 1) * sizeof(int));

    loc->metaID = metaID;
    loc->filenum = filenum;
    loc->frequency = frequency;

    uncompress_location_positions(&p,flag,frequency,loc->posdata);

    return loc;
}


/* 09/00 Jose Ruiz
** Compress all non yet compressed location data of an entry
*/
void    CompressCurrentLocEntry(SWISH * sw, IndexFILE * indexf, ENTRY * e)
{
    LOCATION *l, *prev, *next, *comp;
   
    for(l = e->currentChunkLocationList,prev = NULL ; l != e->currentlocation; )
    {
        next = l->next;
        comp = (LOCATION *) compress_location(sw, indexf, l);
        if(l == e->currentChunkLocationList)
            e->currentChunkLocationList =comp;
        if(prev)
            memcpy(prev, &comp, sizeof(LOCATION *));   /* Use memcpy to avoid alignment problems */
        prev = comp;
        l = next;        
    } 
    e->currentlocation = e->currentChunkLocationList;
}

/* 09/00 Jose Ruiz
** Function to swap location data to a temporal file or ramdisk to save
** memory. Unfortunately we cannot use it with IgnoreLimit option
** enabled.
** The data has been compressed previously in memory.
** Returns the pointer to the file.
*/
void SwapLocData(SWISH * sw, ENTRY *e, unsigned char *buf, int lenbuf)
{
    int     idx_swap_file;
    struct  MOD_Index *idx = sw->Index;

    /* 2002-07 jmruiz - Get de corrsponding swap file */
    /* Get the corresponding hash value to this word  */
    /* IMPORTANT!!!! - The routine being used here to compute the hash */  
    /* must be the same used to store the words */
    /* Then we must get the corresponding swap file index */
    /* Since we cannot have so many swap files (VERYBIGHASHSIZE for verybighash */
    /* routine) we must scale the hash into SWAP_FILES */
    idx_swap_file = (verybighash(e->word) * (MAX_LOC_SWAP_FILES -1))/(VERYBIGHASHSIZE -1);

    if (!idx->fp_loc_write[idx_swap_file])
    {
        idx->fp_loc_write[idx_swap_file] = create_tempfile(sw, F_WRITE_BINARY, "loc", &idx->swap_location_name[idx_swap_file], 0 );
    }

    compress1(lenbuf, idx->fp_loc_write[idx_swap_file], idx->swap_putc);
    if (idx->swap_write(buf, 1, lenbuf, idx->fp_loc_write[idx_swap_file]) != (unsigned int) lenbuf)
    {
        progerr("Cannot write location to swap file");
    }
}

/* 2002-07 jmruiz - New -e schema */
/* Get location data from swap file */
/* If e is null, all data will be restored */
/* If e si not null, only the location for this data will be readed */
void unSwapLocData(SWISH * sw, int idx_swap_file, ENTRY *ep)
{
    unsigned char *buf;
    int     lenbuf;
    struct MOD_Index *idx = sw->Index;
    ENTRY *e;
    LOCATION *l;
    FILE *fp;

    /* Check if some swap file is being used */
    if(!idx->fp_loc_write[idx_swap_file] && !idx->fp_loc_read[idx_swap_file])
       return;

    /* Check if the file is opened for write and close it */
    if(idx->fp_loc_write[idx_swap_file])
    {
        /* Write a 0 to mark the end of locations */
        idx->swap_putc(0,idx->fp_loc_write[idx_swap_file]);
        idx->swap_close(idx->fp_loc_write[idx_swap_file]);
        idx->fp_loc_write[idx_swap_file] = NULL;
    }

    /* Reopen in read mode for (for faster reads, I suppose) */
    if(!idx->fp_loc_read[idx_swap_file])
    {
        if (!(idx->fp_loc_read[idx_swap_file] = fopen(idx->swap_location_name[idx_swap_file], F_READ_BINARY)))
            progerrno("Could not open temp file %s: ", idx->swap_location_name[idx_swap_file]);
    }
    else
    {
        /* File already opened for read -> reset pointer */
        fseek(idx->fp_loc_read[idx_swap_file],0,SEEK_SET);
    }

    fp = idx->fp_loc_read[idx_swap_file];
    while((lenbuf = uncompress1(fp, idx->swap_getc)))
    {
        if(ep == NULL)
        {
            buf = (unsigned char *) Mem_ZoneAlloc(idx->totalLocZone,lenbuf);
            idx->swap_read(buf, lenbuf, 1, fp);
            e = *(ENTRY **)buf;
            /* Store the locations in reverse order - Faster. They will be
            ** sorted later */
            l = (LOCATION *) buf;
            l->next = e->allLocationList;
            e->allLocationList = l;
        }
        else
        {
            idx->swap_read(&e,sizeof(ENTRY *),1,fp);
            if(ep == e)
            {
                buf = (unsigned char *) Mem_ZoneAlloc(idx->totalLocZone,lenbuf);             
                memcpy(buf,&e,sizeof(ENTRY *));
                idx->swap_read(buf + sizeof(ENTRY *),lenbuf - sizeof(ENTRY *),1,fp);
                /* Store the locations in reverse order - Faster. They will be
                ** sorted later */
                l = (LOCATION *) buf;
                l->next = e->allLocationList;
                e->allLocationList = l;
            }
            else
            {
                /* Just advance file pointer */
                idx->swap_seek(fp,lenbuf - sizeof(ENTRY *),SEEK_CUR);
            }
        }
    }
}

/* 2002-07 jmruiz - Sorts unswaped location data by metaname, filenum */
void sortSwapLocData(SWISH * sw, ENTRY *e)
{
    int i, j, k, metaID;
    int    *pi = NULL;
    unsigned char *ptmp,
           *ptmp2,
           *compressed_data;
    LOCATION **tmploc;
    LOCATION *l, *prev=NULL, **lp;

    /* Count the locations */
    for(i = 0, l = e->allLocationList; l;i++, l = l->next);
    
    /* Very trivial case */
    if(i < 2)
        return;

    /* */
    /* Now, let's sort by metanum, offset in file */

    /* Compute array wide for sort */
    j = 2 * sizeof(int) + sizeof(void *);

    /* Compute array size */
    ptmp = (void *) emalloc(j * i);

    /* Build an array with the elements to compare
       and pointers to data */

    /* Very important to remind - data was read from the loc
    ** swap file in reverse order, so, to get data sorted
    ** by filenum we just need to use a reverse counter (i - k)
    ** as the other value for sorting (it has the same effect
    ** as filenum)
    */
    for(k=0, ptmp2 = ptmp, l = e->allLocationList ; k < i; k++, l = l->next)
    {
        pi = (int *) ptmp2;

        compressed_data = (unsigned char *)l;
        /* Jump fileoffset */
        compressed_data += sizeof(LOCATION *);

        metaID = uncompress2(&compressed_data);
        pi[0] = metaID;
        pi[1] = i-k;
        ptmp2 += 2 * sizeof(int);

        lp = (LOCATION **)ptmp2;
        *lp = l;
        ptmp2 += sizeof(void *);
    }

    /* Sort them */
    swish_qsort(ptmp, i, j, &icomp2);

    /* Store results */
    for (k = 0, ptmp2 = ptmp; k < i; k++)
    {
        ptmp2 += 2 * sizeof(int);

        l = *(LOCATION **)ptmp2;
        if(!k)
            e->allLocationList = l;
        else
        {
            tmploc = (LOCATION **)prev;
            *tmploc = l;
        }
        ptmp2 += sizeof(void *);
        prev = l;
    }
    tmploc = (LOCATION **)l;
    *tmploc = NULL;

    /* Free the memory of the sorting array */
    efree(ptmp);
                 
}


1	adcroft	1.1	/*
2			** Copyright (C) 1995, 1996, 1997, 1998 Hewlett-Packard Company
3			** Originally by Kevin Hughes, kev@kevcom.com, 3/11/94
4			**
5			** This program and library is free software; you can redistribute it and/or
6			** modify it under the terms of the GNU (Library) General Public License
7			** as published by the Free Software Foundation; either version 2
8			** of the License, or any later version.
9			**
10			** This program is distributed in the hope that it will be useful,
11			** but WITHOUT ANY WARRANTY; without even the implied warranty of
12			** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13			** GNU (Library) General Public License for more details.
14			**
15			** You should have received a copy of the GNU (Library) General Public License
16			** along with this program; if not, write to the Free Software
17			** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18			**
19			** 2001-02-12 rasc errormsg "print" changed...
20			**
21			*/
22
23			#include "swish.h"
24			#include "string.h"
25			#include "compress.h"
26			#include "mem.h"
27			#include "error.h"
28			#include "merge.h"
29			#include "docprop.h"
30			#include "index.h"
31			#include "search.h"
32			#include "hash.h"
33			#include "ramdisk.h"
34			#include "swish_qsort.h"
35			#include "file.h"
36
37
38			/* 2001-05 jmruiz */
39			/* Routines for compressing numbers - Macros converted to routines */
40
41			/* Compress a number and writes it to a file */
42			void compress1(int num, FILE * fp, int (f_putc) (int, FILE ))
43			{
44			int _i = 0,
45			_r = num;
46			unsigned char _s[MAXINTCOMPSIZE];
47
48			/* Trivial case: 0 */
49			if(!_r)
50			{
51			f_putc(0,fp);
52			return;
53			}
54
55			/* Any other case ... */
56			while (_r)
57			{
58			_s[_i++] = _r & 127;
59			_r >>= 7;
60			}
61			while (--_i >= 0)
62			f_putc(_s[_i] \| (_i ? 128 : 0), fp);
63			}
64
65			/* Compress a number and writes it to a buffer */
66			/* buffer must be previously allocated */
67			/* returns the decreased buffer pointer after storing the compressed number in it */
68			unsigned char SW_compress2(int num, unsigned char buffer)
69			{
70			int _i = num;
71
72			/* Trivial case: 0 */
73			if(!_i)
74			{
75			*buffer-- = 0;
76			return 0;
77			}
78
79			/* Any other case ... */
80			while (_i)
81			{
82			*buffer = _i & 127;
83			if (_i != num)
84			*buffer \|= 128;
85			_i >>= 7;
86			buffer--;
87			}
88
89			return buffer;
90			}
91
92			/* Compress a number and writes it to a buffer */
93			/* buffer must be previously allocated */
94			/* returns the incrmented buffer pointer after storing the compressed number in it */
95			unsigned char compress3(int num, unsigned char buffer)
96			{
97			int _i = 0,
98			_r = num;
99			unsigned char _s[MAXINTCOMPSIZE];
100
101			/* Trivial case: 0 */
102			if(!_r)
103			{
104			*buffer++ = 0;
105			return buffer;
106			}
107
108			/* Any other case ... */
109			while (_r)
110			{
111			_s[_i++] = _r & 127;
112			_r >>= 7;
113			}
114			while (--_i >= 0)
115			*buffer++ = (_s[_i] \| (_i ? 128 : 0));
116
117			return buffer;
118			}
119
120			/* Uncompress a number from a file */
121			int uncompress1(FILE * fp, int (f_getc) (FILE ))
122			{
123			int _c;
124			int num = 0;
125
126			do
127			{
128			_c = (int) f_getc(fp);
129			num <<= 7;
130			num \|= _c & 127;
131			if (!num)
132			break;
133			}
134			while (_c & 128);
135
136			return num;
137			}
138
139			/* same routine but this works with a memory forward buffer instead of file */
140			/* it also increases the buffer pointer */
141			int uncompress2(unsigned char **buffer)
142			{
143			int _c;
144			int num = 0;
145			unsigned char p = buffer;
146
147			do
148			{
149			_c = (int) ((unsigned char) *p++);
150			num <<= 7;
151			num \|= _c & 127;
152			if (!num)
153			break;
154			}
155			while (_c & 128);
156
157			*buffer = p;
158			return num;
159			}
160
161			/* Rourtines to make long integers portable */
162			unsigned long PACKLONG(unsigned long num)
163			{
164			unsigned long _i = 0L;
165			unsigned char *_s;
166
167			if (num)
168			{
169			_s = (unsigned char *) &_i;
170			_s[0] = (unsigned char) ((num >> 24) & 0xFF);
171			_s[1] = (unsigned char) ((num >> 16) & 0xFF);
172			_s[2] = (unsigned char) ((num >> 8) & 0xFF);
173			_s[3] = (unsigned char) (num & 0xFF);
174			return _i;
175			}
176			return num;
177			}
178
179			/* Same routine - Packs long in buffer */
180			void PACKLONG2(unsigned long num, unsigned char *buffer)
181			{
182			buffer[0] = (unsigned char) ((num >> 24) & 0xFF);
183			buffer[1] = (unsigned char) ((num >> 16) & 0xFF);
184			buffer[2] = (unsigned char) ((num >> 8) & 0xFF);
185			buffer[3] = (unsigned char) (num & 0xFF);
186			}
187
188
189			unsigned long UNPACKLONG(unsigned long num)
190			{
191			unsigned char _s = (unsigned char ) &num;
192
193			return (_s[0] << 24) + (_s[1] << 16) + (_s[2] << 8) + _s[3];
194			}
195
196			/* Same macro - UnPacks long from buffer */
197			unsigned long UNPACKLONG2(unsigned char *buffer)
198			{
199			return (buffer[0] << 24) + (buffer[1] << 16) + (buffer[2] << 8) + buffer[3];
200			}
201
202
203
204			/***********************************************************************************
205			* 09/00 Jose Ruiz
206			* Function to compress location data in memory
207			*
208			* Compresses a LOCATION entry
209			*
210			* A single position LOCATION goes from 20 to 3 bytes.
211			* three positions goes from 28 to 5.
212			*
213			************************************************************************************/
214
215			#define IS_FLAG 0x80 /* Binary 10000000 */
216			#define COMMON_STRUCTURE 0x60 /* Binary 01100000 */
217			#define COMMON_IN_FILE 0x20 /* Binary 00100000 */
218			#define COMMON_IN_HTML_BODY 0x40 /* Binary 01000000 */
219			#define POS_4_BIT 0x10 /* Binary 00010000 */
220			/************************************************************************
221
222			From Jose on Feb 13, 2002
223
224			IS_FLAG is to indicate that the byte is a flag. As far as I remember, I
225			needed it to avoid null values.
226
227			When COMMON_STRUCTURE is on, this means that all the positions
228			have the same structure value. This helps a lot with non html
229			files and can save a lot of space.
230
231			When FREQ_AND_POS_EQ_1 is on, this means that freq is 1 and
232			pos[0]=1. Mmm, I am not sure if this is very useful now. Let me
233			explain better. This was useful for xml files with fields that contains
234			just one value. For example:
235			<code>00001</code>
236			<date>20001231</date>
237			But, now, I am not sure if this is useful because long time ago I
238			changed the position counter to not be reseted after a each field
239			change.
240			I need to check this.
241
242			POS_4_BIT indicates that all positions are within 16 positions
243			of each other and can thus be stored as 2 per byte. Position numbers are
244			stored as a delta from the previous position.
245
246			Here's indexing /usr/doc:
247
248
249			23840 files indexed. 177638538 total bytes. 19739102 total words.
250			Elapsed time: 00:04:42 CPU time: 00:03:09
251			Indexing done!
252			4 bit = 843,081 (total length = 10,630,425) 12 bytes/chunk
253			not 4 bit = 13,052,904 (length 83,811,498) 6 bytes/chunk
254
255			I wonder if storing the initial postion would improve that much.
256
257
258
259
260			*************************************************************************/
261
262
263
264
265
266			void compress_location_values(unsigned char buf,unsigned char flagp,int filenum,int frequency, int *posdata)
267			{
268			unsigned char p = buf;
269			unsigned char *flag;
270			int structure = GET_STRUCTURE(posdata[0]);
271			int common_structure = COMMON_STRUCTURE;
272			int i;
273
274			/* Make room for flag and init it */
275			flag = p;
276			*flagp = p;
277			p++;
278
279			*flag = IS_FLAG;
280
281			/* Add file number */
282			p = compress3(filenum, p);
283
284
285			/* Check for special case frequency == 1 and position[0] < 128 && structure == IN_FILE */
286			if(frequency == 1 && (GET_POSITION(posdata[0]) < 128) && structure == IN_FILE)
287			{
288			/* Remove IS_FLAG and store position in the lower 7 bits */
289			/* In this way we have 0bbbbbbb in *flag
290			** where bbbbbbb is the position and the leading 0 bit
291			** indicates that frequency is 1 and position is < 128 */
292			*flag = (unsigned char) ((int)(GET_POSITION(posdata[0])));
293			}
294			else
295			{
296			/* Otherwise IS_FLAG is set */
297			/* Now, let's see if all positions have the same structure to
298			** get better compression */
299			for(i=1;i<frequency;i++)
300			{
301			if(structure != GET_STRUCTURE(posdata[i]))
302			{
303			common_structure = 0;
304			break;
305			}
306			}
307			if(frequency < 16)
308			(flag) \|= frequency; / Store freequency in flag - low 4 bits */
309			else
310			p = compress3(frequency, p); /* Otherwise, leave frequency "as is" */
311			/* Add structure if it is equal for all positions */
312			if(common_structure)
313			{
314			switch(structure)
315			{
316			case IN_FILE:
317			*flag \|= COMMON_IN_FILE;
318			break;
319
320			case IN_BODY \| IN_FILE:
321			*flag \|= COMMON_IN_HTML_BODY;
322			break;
323
324			default:
325			*p++ = (unsigned char) structure;
326			*flag \|= COMMON_STRUCTURE;
327			break;
328			}
329			}
330			}
331			*buf = p;
332			}
333
334			void compress_location_positions(unsigned char *buf,unsigned char flag,int frequency, int *posdata)
335			{
336			unsigned char p = buf;
337			int i, j;
338
339			if((*flag) & IS_FLAG)
340			{
341			(*flag) \|= POS_4_BIT;
342
343			for(i = frequency - 1; i > 0 ; i--)
344			{
345			posdata[i] = SET_POSDATA(GET_POSITION(posdata[i]) - GET_POSITION(posdata[i-1]),GET_STRUCTURE(posdata[i]));
346			if( GET_POSITION(posdata[i]) >= 16)
347			(*flag) &= ~POS_4_BIT;
348			}
349
350			/* Always write first position "as is" */
351			p = compress3(GET_POSITION(posdata[0]), p);
352
353			/* write the position data starting at 1 */
354			if((*flag) & POS_4_BIT)
355			{
356			for (i = 1, j = 0; i < frequency ; i++, j++)
357			{
358			if(j % 2)
359			p[j/2] \|= (unsigned char) GET_POSITION(posdata[i]);
360			else
361			p[j/2] = (unsigned char) GET_POSITION(posdata[i]) << 4;
362			}
363			p += ((j + 1)/2);
364			}
365			else
366			{
367			for (i = 1; i < frequency; i++)
368			p = compress3(GET_POSITION(posdata[i]), p);
369			}
370
371			/* Write out the structure bytes */
372			if(! (*flag & COMMON_STRUCTURE))
373			for(i = 0; i < frequency; i++)
374			*p++ = (unsigned char) GET_STRUCTURE(posdata[i]);
375
376			*buf = p;
377			}
378			}
379
380			unsigned char compress_location(SWISH sw, IndexFILE * indexf, LOCATION * l)
381			{
382			unsigned char *p,
383			*q;
384			int i,
385			max_size;
386			unsigned char *flag;
387			struct MOD_Index *idx = sw->Index;
388
389			/* check if the work buffer is long enough */
390			/* just to avoid bufferoverruns */
391			/* In the worst case and integer will need MAXINTCOMPSIZE bytes */
392			/* but fortunatelly this is very uncommon */
393
394			/* 2002/01 JMRUIZ
395			** Added an extra byte (MAXINTCOMPSIZE+1) for each position's structure
396			*/
397
398			max_size = sizeof(unsigned char) + sizeof(LOCATION ) + (((sizeof(LOCATION) / sizeof(int) + 1) + (l->frequency - 1)) (MAXINTCOMPSIZE + sizeof(unsigned char)));
399
400
401			/* reallocate if needed */
402			if (max_size > idx->len_compression_buffer)
403			{
404			idx->len_compression_buffer = max_size + 200;
405			idx->compression_buffer = erealloc(idx->compression_buffer, idx->len_compression_buffer);
406			}
407
408
409			/* Pointer to the buffer */
410			p = idx->compression_buffer;
411
412			/* Add extra bytes for handling linked list */
413			//***JMRUIZ
414
415			memcpy(p,&l->next,sizeof(LOCATION *));
416			p += sizeof(LOCATION *);
417
418			/* Add the metaID */
419			p = compress3(l->metaID,p);
420
421			compress_location_values(&p,&flag,l->filenum,l->frequency, l->posdata);
422			compress_location_positions(&p,flag,l->frequency,l->posdata);
423
424
425
426			/* Get the length of all the data */
427			i = p - idx->compression_buffer;
428
429
430			/* Did we underrun our buffer? */
431			if (i > idx->len_compression_buffer)
432			progerr("Internal error in compress_location routine");
433
434
435			q = (unsigned char *) Mem_ZoneAlloc(idx->currentChunkLocZone, i);
436			memcpy(q, idx->compression_buffer, i);
437
438			return (unsigned char *) q;
439			}
440
441
442			void uncompress_location_values(unsigned char *buf,unsigned char flag, int filenum,int frequency)
443			{
444			unsigned char p = buf;
445
446			*frequency = 0;
447
448			flag = p++;
449
450			if(!((*flag) & IS_FLAG))
451			{
452			*frequency = 1;
453			}
454			else
455			(frequency) \|= (flag) & 15; /* Binary 00001111 */
456
457			*filenum = uncompress2(&p);
458
459			if(! (*frequency))
460			*frequency = uncompress2(&p);
461
462			*buf = p;
463			}
464
465			unsigned long four_bit_count = 0;
466			unsigned long four_bit_bytes = 0;
467			unsigned long not_four = 0;
468			unsigned long not_four_bytes = 0;
469			unsigned long four_bit_called = 0;
470			unsigned long not_four_called;
471
472
473			void uncompress_location_positions(unsigned char *buf, unsigned char flag, int frequency, int posdata)
474			{
475			int i, j, tmp;
476			unsigned char p = buf;
477			int common_structure = 0;
478			int structure = 0;
479
480			/* Check for special case frequency == 1 and position[0] < 128 and structure == IN_FILE */
481			if (!(flag & IS_FLAG))
482			{
483			structure = IN_FILE;
484			posdata[0] = SET_POSDATA((int)(flag),structure);
485			}
486			else
487			{
488			/* Check for common structure */
489			if ((tmp =(flag & COMMON_STRUCTURE)))
490			{
491			common_structure = COMMON_STRUCTURE;
492			switch(tmp)
493			{
494			case COMMON_IN_FILE:
495			structure = IN_FILE;
496			break;
497
498			case COMMON_IN_HTML_BODY:
499			structure = IN_FILE \| IN_BODY;
500			break;
501
502			default:
503			structure = (int)((unsigned char) *p++);
504			break;
505			}
506			}
507
508			/* First position is always "as is" */
509			posdata[0] = uncompress2(&p);
510
511			/* Check if positions where stored as two values per byte or the old "compress" style */
512			if(flag & POS_4_BIT)
513			{
514			for (i = 1, j = 0; i < frequency; i++, j++)
515			{
516			if(j%2)
517			posdata[i] = p[j/2] & 0x0F;
518			else
519			posdata[i] = p[j/2] >> 4;
520			}
521			p += ((j + 1)/2);
522			}
523			else
524			{
525			for (i = 1; i < frequency; i++)
526			{
527			tmp = uncompress2(&p);
528			posdata[i] = tmp;
529			}
530			}
531			/* Position were compressed incrementally. So restore them */
532			for(i = 1; i < frequency; i++)
533			posdata[i] += posdata[i-1];
534
535			/* Get structure */
536			for(i = 0; i < frequency; i++)
537			{
538			if(!common_structure)
539			structure = (int)((unsigned char) *p++);
540
541			posdata[i] = SET_POSDATA(posdata[i],structure);
542			}
543			}
544			/* Update buffer pointer */
545			*buf = p;
546			}
547
548			/* 09/00 Jose Ruiz
549			** Extract compressed location
550			*/
551			LOCATION uncompress_location(SWISH sw, IndexFILE * indexf, unsigned char *p)
552			{
553			LOCATION *loc;
554			int metaID,
555			filenum,
556			frequency;
557			unsigned char flag;
558
559			metaID = uncompress2(&p);
560
561			uncompress_location_values(&p,&flag,&filenum,&frequency);
562
563			loc = (LOCATION ) emalloc(sizeof(LOCATION) + (frequency - 1) sizeof(int));
564
565			loc->metaID = metaID;
566			loc->filenum = filenum;
567			loc->frequency = frequency;
568
569			uncompress_location_positions(&p,flag,frequency,loc->posdata);
570
571			return loc;
572			}
573
574
575			/* 09/00 Jose Ruiz
576			** Compress all non yet compressed location data of an entry
577			*/
578			void CompressCurrentLocEntry(SWISH * sw, IndexFILE * indexf, ENTRY * e)
579			{
580			LOCATION l, prev, next, comp;
581
582			for(l = e->currentChunkLocationList,prev = NULL ; l != e->currentlocation; )
583			{
584			next = l->next;
585			comp = (LOCATION *) compress_location(sw, indexf, l);
586			if(l == e->currentChunkLocationList)
587			e->currentChunkLocationList =comp;
588			if(prev)
589			memcpy(prev, &comp, sizeof(LOCATION )); / Use memcpy to avoid alignment problems */
590			prev = comp;
591			l = next;
592			}
593			e->currentlocation = e->currentChunkLocationList;
594			}
595
596			/* 09/00 Jose Ruiz
597			** Function to swap location data to a temporal file or ramdisk to save
598			** memory. Unfortunately we cannot use it with IgnoreLimit option
599			** enabled.
600			** The data has been compressed previously in memory.
601			** Returns the pointer to the file.
602			*/
603			void SwapLocData(SWISH * sw, ENTRY e, unsigned char buf, int lenbuf)
604			{
605			int idx_swap_file;
606			struct MOD_Index *idx = sw->Index;
607
608			/* 2002-07 jmruiz - Get de corrsponding swap file */
609			/* Get the corresponding hash value to this word */
610			/* IMPORTANT!!!! - The routine being used here to compute the hash */
611			/* must be the same used to store the words */
612			/* Then we must get the corresponding swap file index */
613			/* Since we cannot have so many swap files (VERYBIGHASHSIZE for verybighash */
614			/* routine) we must scale the hash into SWAP_FILES */
615			idx_swap_file = (verybighash(e->word) * (MAX_LOC_SWAP_FILES -1))/(VERYBIGHASHSIZE -1);
616
617			if (!idx->fp_loc_write[idx_swap_file])
618			{
619			idx->fp_loc_write[idx_swap_file] = create_tempfile(sw, F_WRITE_BINARY, "loc", &idx->swap_location_name[idx_swap_file], 0 );
620			}
621
622			compress1(lenbuf, idx->fp_loc_write[idx_swap_file], idx->swap_putc);
623			if (idx->swap_write(buf, 1, lenbuf, idx->fp_loc_write[idx_swap_file]) != (unsigned int) lenbuf)
624			{
625			progerr("Cannot write location to swap file");
626			}
627			}
628
629			/* 2002-07 jmruiz - New -e schema */
630			/* Get location data from swap file */
631			/* If e is null, all data will be restored */
632			/* If e si not null, only the location for this data will be readed */
633			void unSwapLocData(SWISH * sw, int idx_swap_file, ENTRY *ep)
634			{
635			unsigned char *buf;
636			int lenbuf;
637			struct MOD_Index *idx = sw->Index;
638			ENTRY *e;
639			LOCATION *l;
640			FILE *fp;
641
642			/* Check if some swap file is being used */
643			if(!idx->fp_loc_write[idx_swap_file] && !idx->fp_loc_read[idx_swap_file])
644			return;
645
646			/* Check if the file is opened for write and close it */
647			if(idx->fp_loc_write[idx_swap_file])
648			{
649			/* Write a 0 to mark the end of locations */
650			idx->swap_putc(0,idx->fp_loc_write[idx_swap_file]);
651			idx->swap_close(idx->fp_loc_write[idx_swap_file]);
652			idx->fp_loc_write[idx_swap_file] = NULL;
653			}
654
655			/* Reopen in read mode for (for faster reads, I suppose) */
656			if(!idx->fp_loc_read[idx_swap_file])
657			{
658			if (!(idx->fp_loc_read[idx_swap_file] = fopen(idx->swap_location_name[idx_swap_file], F_READ_BINARY)))
659			progerrno("Could not open temp file %s: ", idx->swap_location_name[idx_swap_file]);
660			}
661			else
662			{
663			/* File already opened for read -> reset pointer */
664			fseek(idx->fp_loc_read[idx_swap_file],0,SEEK_SET);
665			}
666
667			fp = idx->fp_loc_read[idx_swap_file];
668			while((lenbuf = uncompress1(fp, idx->swap_getc)))
669			{
670			if(ep == NULL)
671			{
672			buf = (unsigned char *) Mem_ZoneAlloc(idx->totalLocZone,lenbuf);
673			idx->swap_read(buf, lenbuf, 1, fp);
674			e = (ENTRY *)buf;
675			/* Store the locations in reverse order - Faster. They will be
676			** sorted later */
677			l = (LOCATION *) buf;
678			l->next = e->allLocationList;
679			e->allLocationList = l;
680			}
681			else
682			{
683			idx->swap_read(&e,sizeof(ENTRY *),1,fp);
684			if(ep == e)
685			{
686			buf = (unsigned char *) Mem_ZoneAlloc(idx->totalLocZone,lenbuf);
687			memcpy(buf,&e,sizeof(ENTRY *));
688			idx->swap_read(buf + sizeof(ENTRY ),lenbuf - sizeof(ENTRY ),1,fp);
689			/* Store the locations in reverse order - Faster. They will be
690			** sorted later */
691			l = (LOCATION *) buf;
692			l->next = e->allLocationList;
693			e->allLocationList = l;
694			}
695			else
696			{
697			/* Just advance file pointer */
698			idx->swap_seek(fp,lenbuf - sizeof(ENTRY *),SEEK_CUR);
699			}
700			}
701			}
702			}
703
704			/* 2002-07 jmruiz - Sorts unswaped location data by metaname, filenum */
705			void sortSwapLocData(SWISH * sw, ENTRY *e)
706			{
707			int i, j, k, metaID;
708			int *pi = NULL;
709			unsigned char *ptmp,
710			*ptmp2,
711			*compressed_data;
712			LOCATION **tmploc;
713			LOCATION l, prev=NULL, **lp;
714
715			/* Count the locations */
716			for(i = 0, l = e->allLocationList; l;i++, l = l->next);
717
718			/* Very trivial case */
719			if(i < 2)
720			return;
721
722			/* */
723			/* Now, let's sort by metanum, offset in file */
724
725			/* Compute array wide for sort */
726			j = 2 * sizeof(int) + sizeof(void *);
727
728			/* Compute array size */
729			ptmp = (void ) emalloc(j i);
730
731			/* Build an array with the elements to compare
732			and pointers to data */
733
734			/* Very important to remind - data was read from the loc
735			** swap file in reverse order, so, to get data sorted
736			** by filenum we just need to use a reverse counter (i - k)
737			** as the other value for sorting (it has the same effect
738			** as filenum)
739			*/
740			for(k=0, ptmp2 = ptmp, l = e->allLocationList ; k < i; k++, l = l->next)
741			{
742			pi = (int *) ptmp2;
743
744			compressed_data = (unsigned char *)l;
745			/* Jump fileoffset */
746			compressed_data += sizeof(LOCATION *);
747
748			metaID = uncompress2(&compressed_data);
749			pi[0] = metaID;
750			pi[1] = i-k;
751			ptmp2 += 2 * sizeof(int);
752
753			lp = (LOCATION **)ptmp2;
754			*lp = l;
755			ptmp2 += sizeof(void *);
756			}
757
758			/* Sort them */
759			swish_qsort(ptmp, i, j, &icomp2);
760
761			/* Store results */
762			for (k = 0, ptmp2 = ptmp; k < i; k++)
763			{
764			ptmp2 += 2 * sizeof(int);
765
766			l = (LOCATION *)ptmp2;
767			if(!k)
768			e->allLocationList = l;
769			else
770			{
771			tmploc = (LOCATION **)prev;
772			*tmploc = l;
773			}
774			ptmp2 += sizeof(void *);
775			prev = l;
776			}
777			tmploc = (LOCATION **)l;
778			*tmploc = NULL;
779
780			/* Free the memory of the sorting array */
781			efree(ptmp);
782
783			}
784
785
786
787
788
789