1/*
2Copyright (c) 2006-2009, Salvatore Sanfilippo
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
6
7 * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
9 * Neither the name of Smaz nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
10
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
12*/
13
14#include <string.h>
15
16/* Our compression codebook, used for compression */
17static const char *Smaz_cb[241] = {
18"\002s,\266", "\003had\232\002leW", "\003on \216", "", "\001yS",
19"\002ma\255\002li\227", "\003or \260", "", "\002ll\230\003s t\277",
20"\004fromg\002mel", "", "\003its\332", "\001z\333", "\003ingF", "\001>\336",
21"\001 \000\003 (\002nc\344", "\002nd=\003 on\312",
22"\002ne\213\003hat\276\003re q", "", "\002ngT\003herz\004have\306\003s o\225",
23"", "\003ionk\003s a\254\002ly\352", "\003hisL\003 inN\003 be\252", "",
24"\003 fo\325\003 of \003 ha\311", "", "\002of\005",
25"\003 co\241\002no\267\003 ma\370", "", "", "\003 cl\356\003enta\003 an7",
26"\002ns\300\001\"e", "\003n t\217\002ntP\003s, \205",
27"\002pe\320\003 we\351\002om\223", "\002on\037", "", "\002y G", "\003 wa\271",
28"\003 re\321\002or*", "", "\002=\"\251\002ot\337", "\003forD\002ou[",
29"\003 toR", "\003 th\r", "\003 it\366",
30"\003but\261\002ra\202\003 wi\363\002</\361", "\003 wh\237", "\002 4",
31"\003nd ?", "\002re!", "", "\003ng c", "",
32"\003ly \307\003ass\323\001a\004\002rir", "", "", "", "\002se_", "\003of \"",
33"\003div\364\002ros\003ere\240", "", "\002ta\310\001bZ\002si\324", "",
34"\003and\a\002rs\335", "\002rt\362", "\002teE", "\003ati\316", "\002so\263",
35"\002th\021", "\002tiJ\001c\034\003allp", "\003ate\345", "\002ss\246",
36"\002stM", "", "\002><\346", "\002to\024", "\003arew", "\001d\030",
37"\002tr\303", "", "\001\n1\003 a \222", "\003f tv\002veo", "\002un\340", "",
38"\003e o\242", "\002a \243\002wa\326\001e\002", "\002ur\226\003e a\274",
39"\002us\244\003\n\r\n\247", "\002ut\304\003e c\373", "\002we\221", "", "",
40"\002wh\302", "\001f,", "", "", "", "\003d t\206", "", "", "\003th \343",
41"\001g;", "", "", "\001\r9\003e s\265", "\003e t\234", "", "\003to Y",
42"\003e\r\n\236", "\002d \036\001h\022", "", "\001,Q", "\002 a\031", "\002 b^",
43"\002\r\n\025\002 cI", "\002 d\245", "\002 e\253", "\002 fh\001i\b\002e \v",
44"", "\002 hU\001-\314", "\002 i8", "", "", "\002 l\315", "\002 m{",
45"\002f :\002 n\354", "\002 o\035", "\002 p}\001.n\003\r\n\r\250", "",
46"\002 r\275", "\002 s>", "\002 t\016", "", "\002g \235\005which+\003whi\367",
47"\002 w5", "\001/\305", "\003as \214", "\003at \207", "", "\003who\331", "",
48"\001l\026\002h \212", "", "\002, $", "", "\004withV", "", "", "", "\001m-", "",
49"", "\002ac\357", "\002ad\350", "\003TheH", "", "", "\004this\233\001n\t",
50"", "\002. y", "", "\002alX\003e, \365", "\003tio\215\002be\\",
51"\002an\032\003ver\347", "", "\004that0\003tha\313\001o\006", "\003was2",
52"\002arO", "\002as.", "\002at'\003the\001\004they\200\005there\322\005theird",
53"\002ce\210", "\004were]", "", "\002ch\231\002l \264\001p<", "", "",
54"\003one\256", "", "\003he \023\002dej", "\003ter\270", "\002cou", "",
55"\002by\177\002di\201\002eax", "", "\002ec\327", "\002edB", "\002ee\353", "",
56"", "\001r\f\002n )", "", "", "", "\002el\262", "", "\003in i\002en3", "",
57"\002o `\001s\n", "", "\002er\033", "\003is t\002es6", "", "\002ge\371",
58"\004.com\375", "\002fo\334\003our\330", "\003ch \301\001t\003", "\002hab", "",
59"\003men\374", "", "\002he\020", "", "", "\001u&", "\002hif", "",
60"\003not\204\002ic\203", "\003ed @\002id\355", "", "", "\002ho\273",
61"\002r K\001vm", "", "", "", "\003t t\257\002il\360", "\002im\342",
62"\003en \317\002in\017", "\002io\220", "\002s \027\001wA", "", "\003er |",
63"\003es ~\002is%", "\002it/", "", "\002iv\272", "",
64"\002t #\ahttp://C\001x\372", "\002la\211", "\001<\341", "\003, a\224"
65};
66
67/* Reverse compression codebook, used for decompression */
68static char *Smaz_rcb[254] = {
69" ", "the", "e", "t", "a", "of", "o", "and", "i", "n", "s", "e ", "r", " th",
70" t", "in", "he", "th", "h", "he ", "to", "\r\n", "l", "s ", "d", " a", "an",
71"er", "c", " o", "d ", "on", " of", "re", "of ", "t ", ", ", "is", "u", "at",
72" ", "n ", "or", "which", "f", "m", "as", "it", "that", "\n", "was", "en",
73" ", " w", "es", " an", " i", "\r", "f ", "g", "p", "nd", " s", "nd ", "ed ",
74"w", "ed", "http://", "for", "te", "ing", "y ", "The", " c", "ti", "r ", "his",
75"st", " in", "ar", "nt", ",", " to", "y", "ng", " h", "with", "le", "al", "to ",
76"b", "ou", "be", "were", " b", "se", "o ", "ent", "ha", "ng ", "their", "\"",
77"hi", "from", " f", "in ", "de", "ion", "me", "v", ".", "ve", "all", "re ",
78"ri", "ro", "is ", "co", "f t", "are", "ea", ". ", "her", " m", "er ", " p",
79"es ", "by", "they", "di", "ra", "ic", "not", "s, ", "d t", "at ", "ce", "la",
80"h ", "ne", "as ", "tio", "on ", "n t", "io", "we", " a ", "om", ", a", "s o",
81"ur", "li", "ll", "ch", "had", "this", "e t", "g ", "e\r\n", " wh", "ere",
82" co", "e o", "a ", "us", " d", "ss", "\n\r\n", "\r\n\r", "=\"", " be", " e",
83"s a", "ma", "one", "t t", "or ", "but", "el", "so", "l ", "e s", "s,", "no",
84"ter", " wa", "iv", "ho", "e a", " r", "hat", "s t", "ns", "ch ", "wh", "tr",
85"ut", "/", "have", "ly ", "ta", " ha", " on", "tha", "-", " l", "ati", "en ",
86"pe", " re", "there", "ass", "si", " fo", "wa", "ec", "our", "who", "its", "z",
87"fo", "rs", ">", "ot", "un", "<", "im", "th ", "nc", "ate", "><", "ver", "ad",
88" we", "ly", "ee", " n", "id", " cl", "ac", "il", "</", "rt", " wi", "div",
89"e, ", " it", "whi", " ma", "ge", "x", "e c", "men", ".com"
90};
91
92int smaz_compress(const char *in, int inlen, char *out, int outlen) {
93 unsigned int h1,h2,h3=0;
94 int verblen = 0, _outlen = outlen;
95 char verb[256], *_out = out;
96
97 while(inlen) {
98 int j = 7, needed;
99 char *flush = NULL;
100 char *slot;
101
102 h1 = h2 = in[0]<<3;
103 if (inlen > 1) h2 += in[1];
104 if (inlen > 2) h3 = h2^in[2];
105 if (j > inlen) j = inlen;
106
107 /* Try to lookup substrings into the hash table, starting from the
108 * longer to the shorter substrings */
109 for (; j > 0; j--) {
110 switch(j) {
111 case 1: slot = Smaz_cb[h1%241]; break;
112 case 2: slot = Smaz_cb[h2%241]; break;
113 default: slot = Smaz_cb[h3%241]; break;
114 }
115 while(slot[0]) {
116 if (slot[0] == j && memcmp(slot+1,in,j) == 0) {
117 /* Match found in the hash table,
118 * prepare a verbatim bytes flush if needed */
119 if (verblen) {
120 needed = (verblen == 1) ? 2 : 2+verblen;
121 flush = out;
122 out += needed;
123 outlen -= needed;
124 }
125 /* Emit the byte */
126 if (outlen <= 0) return _outlen+1;
127 out[0] = slot[slot[0]+1];
128 out++;
129 outlen--;
130 inlen -= j;
131 in += j;
132 goto out;
133 } else {
134 slot += slot[0]+2;
135 }
136 }
137 }
138 /* Match not found - add the byte to the verbatim buffer */
139 verb[verblen] = in[0];
140 verblen++;
141 inlen--;
142 in++;
143out:
144 /* Prepare a flush if we reached the flush length limit, and there
145 * is not already a pending flush operation. */
146 if (!flush && (verblen == 256 || (verblen > 0 && inlen == 0))) {
147 needed = (verblen == 1) ? 2 : 2+verblen;
148 flush = out;
149 out += needed;
150 outlen -= needed;
151 if (outlen < 0) return _outlen+1;
152 }
153 /* Perform a verbatim flush if needed */
154 if (flush) {
155 if (verblen == 1) {
156 flush[0] = (signed char)254;
157 flush[1] = verb[0];
158 } else {
159 flush[0] = (signed char)255;
160 flush[1] = (signed char)(verblen-1);
161 memcpy(flush+2,verb,verblen);
162 }
163 flush = NULL;
164 verblen = 0;
165 }
166 }
167 return out-_out;
168}
169
170int smaz_decompress(const char *in, int inlen, char *out, int outlen) {
171 unsigned char *c = (unsigned char*) in;
172 char *_out = out;
173 int _outlen = outlen;
174
175 while(inlen) {
176 if (*c == 254) {
177 /* Verbatim byte */
178 if (outlen < 1) return _outlen+1;
179 *out = *(c+1);
180 out++;
181 outlen--;
182 c += 2;
183 inlen -= 2;
184 } else if (*c == 255) {
185 /* Verbatim string */
186 int len = (*(c+1))+1;
187 if (outlen < len) return _outlen+1;
188 memcpy(out,c+2,len);
189 out += len;
190 outlen -= len;
191 c += 2+len;
192 inlen -= 2+len;
193 } else {
194 /* Codebook entry */
195 const char *s = Smaz_rcb[*c];
196 int len = strlen(s);
197
198 if (outlen < len) return _outlen+1;
199 memcpy(out,s,len);
200 out += len;
201 outlen -= len;
202 c++;
203 inlen--;
204 }
205 }
206 return out-_out;
207}
208