bsd_comp.c 29 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171
  1. /*
  2. * Update: The Berkeley copyright was changed, and the change
  3. * is retroactive to all "true" BSD software (ie everything
  4. * from UCB as opposed to other peoples code that just carried
  5. * the same license). The new copyright doesn't clash with the
  6. * GPL, so the module-only restriction has been removed..
  7. */
  8. /* Because this code is derived from the 4.3BSD compress source:
  9. *
  10. * Copyright (c) 1985, 1986 The Regents of the University of California.
  11. * All rights reserved.
  12. *
  13. * This code is derived from software contributed to Berkeley by
  14. * James A. Woods, derived from original work by Spencer Thomas
  15. * and Joseph Orost.
  16. *
  17. * Redistribution and use in source and binary forms, with or without
  18. * modification, are permitted provided that the following conditions
  19. * are met:
  20. * 1. Redistributions of source code must retain the above copyright
  21. * notice, this list of conditions and the following disclaimer.
  22. * 2. Redistributions in binary form must reproduce the above copyright
  23. * notice, this list of conditions and the following disclaimer in the
  24. * documentation and/or other materials provided with the distribution.
  25. * 3. All advertising materials mentioning features or use of this software
  26. * must display the following acknowledgement:
  27. * This product includes software developed by the University of
  28. * California, Berkeley and its contributors.
  29. * 4. Neither the name of the University nor the names of its contributors
  30. * may be used to endorse or promote products derived from this software
  31. * without specific prior written permission.
  32. *
  33. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  34. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  35. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  36. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  37. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  38. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  39. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  40. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  41. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  42. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  43. * SUCH DAMAGE.
  44. */
  45. /*
  46. * This version is for use with contiguous buffers on Linux-derived systems.
  47. *
  48. * ==FILEVERSION 20000226==
  49. *
  50. * NOTE TO MAINTAINERS:
  51. * If you modify this file at all, please set the number above to the
  52. * date of the modification as YYMMDD (year month day).
  53. * bsd_comp.c is shipped with a PPP distribution as well as with
  54. * the kernel; if everyone increases the FILEVERSION number above,
  55. * then scripts can do the right thing when deciding whether to
  56. * install a new bsd_comp.c file. Don't change the format of that
  57. * line otherwise, so the installation script can recognize it.
  58. *
  59. * From: bsd_comp.c,v 1.3 1994/12/08 01:59:58 paulus Exp
  60. */
  61. #include <linux/module.h>
  62. #include <linux/init.h>
  63. #include <linux/slab.h>
  64. #include <linux/vmalloc.h>
  65. #include <linux/string.h>
  66. #include <linux/ppp_defs.h>
  67. #undef PACKETPTR
  68. #define PACKETPTR 1
  69. #include <linux/ppp-comp.h>
  70. #undef PACKETPTR
  71. #include <asm/byteorder.h>
  72. /*
  73. * PPP "BSD compress" compression
  74. * The differences between this compression and the classic BSD LZW
  75. * source are obvious from the requirement that the classic code worked
  76. * with files while this handles arbitrarily long streams that
  77. * are broken into packets. They are:
  78. *
  79. * When the code size expands, a block of junk is not emitted by
  80. * the compressor and not expected by the decompressor.
  81. *
  82. * New codes are not necessarily assigned every time an old
  83. * code is output by the compressor. This is because a packet
  84. * end forces a code to be emitted, but does not imply that a
  85. * new sequence has been seen.
  86. *
  87. * The compression ratio is checked at the first end of a packet
  88. * after the appropriate gap. Besides simplifying and speeding
  89. * things up, this makes it more likely that the transmitter
  90. * and receiver will agree when the dictionary is cleared when
  91. * compression is not going well.
  92. */
  93. /*
  94. * Macros to extract protocol version and number of bits
  95. * from the third byte of the BSD Compress CCP configuration option.
  96. */
  97. #define BSD_VERSION(x) ((x) >> 5)
  98. #define BSD_NBITS(x) ((x) & 0x1F)
  99. #define BSD_CURRENT_VERSION 1
  100. /*
  101. * A dictionary for doing BSD compress.
  102. */
  103. struct bsd_dict {
  104. union { /* hash value */
  105. unsigned long fcode;
  106. struct {
  107. #if defined(__LITTLE_ENDIAN) /* Little endian order */
  108. unsigned short prefix; /* preceding code */
  109. unsigned char suffix; /* last character of new code */
  110. unsigned char pad;
  111. #elif defined(__BIG_ENDIAN) /* Big endian order */
  112. unsigned char pad;
  113. unsigned char suffix; /* last character of new code */
  114. unsigned short prefix; /* preceding code */
  115. #else
  116. #error Endianness not defined...
  117. #endif
  118. } hs;
  119. } f;
  120. unsigned short codem1; /* output of hash table -1 */
  121. unsigned short cptr; /* map code to hash table entry */
  122. };
  123. struct bsd_db {
  124. int totlen; /* length of this structure */
  125. unsigned int hsize; /* size of the hash table */
  126. unsigned char hshift; /* used in hash function */
  127. unsigned char n_bits; /* current bits/code */
  128. unsigned char maxbits; /* maximum bits/code */
  129. unsigned char debug; /* non-zero if debug desired */
  130. unsigned char unit; /* ppp unit number */
  131. unsigned short seqno; /* sequence # of next packet */
  132. unsigned int mru; /* size of receive (decompress) bufr */
  133. unsigned int maxmaxcode; /* largest valid code */
  134. unsigned int max_ent; /* largest code in use */
  135. unsigned int in_count; /* uncompressed bytes, aged */
  136. unsigned int bytes_out; /* compressed bytes, aged */
  137. unsigned int ratio; /* recent compression ratio */
  138. unsigned int checkpoint; /* when to next check the ratio */
  139. unsigned int clear_count; /* times dictionary cleared */
  140. unsigned int incomp_count; /* incompressible packets */
  141. unsigned int incomp_bytes; /* incompressible bytes */
  142. unsigned int uncomp_count; /* uncompressed packets */
  143. unsigned int uncomp_bytes; /* uncompressed bytes */
  144. unsigned int comp_count; /* compressed packets */
  145. unsigned int comp_bytes; /* compressed bytes */
  146. unsigned short *lens; /* array of lengths of codes */
  147. struct bsd_dict *dict; /* dictionary */
  148. };
  149. #define BSD_OVHD 2 /* BSD compress overhead/packet */
  150. #define MIN_BSD_BITS 9
  151. #define BSD_INIT_BITS MIN_BSD_BITS
  152. #define MAX_BSD_BITS 15
  153. static void bsd_free (void *state);
  154. static void *bsd_alloc(unsigned char *options, int opt_len, int decomp);
  155. static void *bsd_comp_alloc (unsigned char *options, int opt_len);
  156. static void *bsd_decomp_alloc (unsigned char *options, int opt_len);
  157. static int bsd_init (void *db, unsigned char *options,
  158. int opt_len, int unit, int debug, int decomp);
  159. static int bsd_comp_init (void *state, unsigned char *options,
  160. int opt_len, int unit, int opthdr, int debug);
  161. static int bsd_decomp_init (void *state, unsigned char *options,
  162. int opt_len, int unit, int opthdr, int mru,
  163. int debug);
  164. static void bsd_reset (void *state);
  165. static void bsd_comp_stats (void *state, struct compstat *stats);
  166. static int bsd_compress (void *state, unsigned char *rptr,
  167. unsigned char *obuf, int isize, int osize);
  168. static void bsd_incomp (void *state, unsigned char *ibuf, int icnt);
  169. static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
  170. unsigned char *obuf, int osize);
  171. /* These are in ppp_generic.c */
  172. extern int ppp_register_compressor (struct compressor *cp);
  173. extern void ppp_unregister_compressor (struct compressor *cp);
  174. /*
  175. * the next two codes should not be changed lightly, as they must not
  176. * lie within the contiguous general code space.
  177. */
  178. #define CLEAR 256 /* table clear output code */
  179. #define FIRST 257 /* first free entry */
  180. #define LAST 255
  181. #define MAXCODE(b) ((1 << (b)) - 1)
  182. #define BADCODEM1 MAXCODE(MAX_BSD_BITS)
  183. #define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \
  184. ^ (unsigned long)(prefix))
  185. #define BSD_KEY(prefix,suffix) ((((unsigned long)(suffix)) << 16) \
  186. + (unsigned long)(prefix))
  187. #define CHECK_GAP 10000 /* Ratio check interval */
  188. #define RATIO_SCALE_LOG 8
  189. #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
  190. #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
  191. /*
  192. * clear the dictionary
  193. */
  194. static void
  195. bsd_clear(struct bsd_db *db)
  196. {
  197. db->clear_count++;
  198. db->max_ent = FIRST-1;
  199. db->n_bits = BSD_INIT_BITS;
  200. db->bytes_out = 0;
  201. db->in_count = 0;
  202. db->ratio = 0;
  203. db->checkpoint = CHECK_GAP;
  204. }
  205. /*
  206. * If the dictionary is full, then see if it is time to reset it.
  207. *
  208. * Compute the compression ratio using fixed-point arithmetic
  209. * with 8 fractional bits.
  210. *
  211. * Since we have an infinite stream instead of a single file,
  212. * watch only the local compression ratio.
  213. *
  214. * Since both peers must reset the dictionary at the same time even in
  215. * the absence of CLEAR codes (while packets are incompressible), they
  216. * must compute the same ratio.
  217. */
  218. static int bsd_check (struct bsd_db *db) /* 1=output CLEAR */
  219. {
  220. unsigned int new_ratio;
  221. if (db->in_count >= db->checkpoint)
  222. {
  223. /* age the ratio by limiting the size of the counts */
  224. if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
  225. {
  226. db->in_count -= (db->in_count >> 2);
  227. db->bytes_out -= (db->bytes_out >> 2);
  228. }
  229. db->checkpoint = db->in_count + CHECK_GAP;
  230. if (db->max_ent >= db->maxmaxcode)
  231. {
  232. /* Reset the dictionary only if the ratio is worse,
  233. * or if it looks as if it has been poisoned
  234. * by incompressible data.
  235. *
  236. * This does not overflow, because
  237. * db->in_count <= RATIO_MAX.
  238. */
  239. new_ratio = db->in_count << RATIO_SCALE_LOG;
  240. if (db->bytes_out != 0)
  241. {
  242. new_ratio /= db->bytes_out;
  243. }
  244. if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
  245. {
  246. bsd_clear (db);
  247. return 1;
  248. }
  249. db->ratio = new_ratio;
  250. }
  251. }
  252. return 0;
  253. }
  254. /*
  255. * Return statistics.
  256. */
  257. static void bsd_comp_stats (void *state, struct compstat *stats)
  258. {
  259. struct bsd_db *db = (struct bsd_db *) state;
  260. stats->unc_bytes = db->uncomp_bytes;
  261. stats->unc_packets = db->uncomp_count;
  262. stats->comp_bytes = db->comp_bytes;
  263. stats->comp_packets = db->comp_count;
  264. stats->inc_bytes = db->incomp_bytes;
  265. stats->inc_packets = db->incomp_count;
  266. stats->in_count = db->in_count;
  267. stats->bytes_out = db->bytes_out;
  268. }
  269. /*
  270. * Reset state, as on a CCP ResetReq.
  271. */
  272. static void bsd_reset (void *state)
  273. {
  274. struct bsd_db *db = (struct bsd_db *) state;
  275. bsd_clear(db);
  276. db->seqno = 0;
  277. db->clear_count = 0;
  278. }
  279. /*
  280. * Release the compression structure
  281. */
  282. static void bsd_free (void *state)
  283. {
  284. struct bsd_db *db = state;
  285. if (!db)
  286. return;
  287. /*
  288. * Release the dictionary
  289. */
  290. vfree(db->dict);
  291. db->dict = NULL;
  292. /*
  293. * Release the string buffer
  294. */
  295. vfree(db->lens);
  296. db->lens = NULL;
  297. /*
  298. * Finally release the structure itself.
  299. */
  300. kfree(db);
  301. }
  302. /*
  303. * Allocate space for a (de) compressor.
  304. */
  305. static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
  306. {
  307. int bits;
  308. unsigned int hsize, hshift, maxmaxcode;
  309. struct bsd_db *db;
  310. if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
  311. || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  312. {
  313. return NULL;
  314. }
  315. bits = BSD_NBITS(options[2]);
  316. switch (bits)
  317. {
  318. case 9: /* needs 82152 for both directions */
  319. case 10: /* needs 84144 */
  320. case 11: /* needs 88240 */
  321. case 12: /* needs 96432 */
  322. hsize = 5003;
  323. hshift = 4;
  324. break;
  325. case 13: /* needs 176784 */
  326. hsize = 9001;
  327. hshift = 5;
  328. break;
  329. case 14: /* needs 353744 */
  330. hsize = 18013;
  331. hshift = 6;
  332. break;
  333. case 15: /* needs 691440 */
  334. hsize = 35023;
  335. hshift = 7;
  336. break;
  337. case 16: /* needs 1366160--far too much, */
  338. /* hsize = 69001; */ /* and 69001 is too big for cptr */
  339. /* hshift = 8; */ /* in struct bsd_db */
  340. /* break; */
  341. default:
  342. return NULL;
  343. }
  344. /*
  345. * Allocate the main control structure for this instance.
  346. */
  347. maxmaxcode = MAXCODE(bits);
  348. db = kzalloc(sizeof (struct bsd_db),
  349. GFP_KERNEL);
  350. if (!db)
  351. {
  352. return NULL;
  353. }
  354. /*
  355. * Allocate space for the dictionary. This may be more than one page in
  356. * length.
  357. */
  358. db->dict = vmalloc(array_size(hsize, sizeof(struct bsd_dict)));
  359. if (!db->dict)
  360. {
  361. bsd_free (db);
  362. return NULL;
  363. }
  364. /*
  365. * If this is the compression buffer then there is no length data.
  366. */
  367. if (!decomp)
  368. {
  369. db->lens = NULL;
  370. }
  371. /*
  372. * For decompression, the length information is needed as well.
  373. */
  374. else
  375. {
  376. db->lens = vmalloc(array_size(sizeof(db->lens[0]), (maxmaxcode + 1)));
  377. if (!db->lens)
  378. {
  379. bsd_free (db);
  380. return NULL;
  381. }
  382. }
  383. /*
  384. * Initialize the data information for the compression code
  385. */
  386. db->totlen = sizeof (struct bsd_db) +
  387. (sizeof (struct bsd_dict) * hsize);
  388. db->hsize = hsize;
  389. db->hshift = hshift;
  390. db->maxmaxcode = maxmaxcode;
  391. db->maxbits = bits;
  392. return (void *) db;
  393. }
  394. static void *bsd_comp_alloc (unsigned char *options, int opt_len)
  395. {
  396. return bsd_alloc (options, opt_len, 0);
  397. }
  398. static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
  399. {
  400. return bsd_alloc (options, opt_len, 1);
  401. }
  402. /*
  403. * Initialize the database.
  404. */
  405. static int bsd_init (void *state, unsigned char *options,
  406. int opt_len, int unit, int debug, int decomp)
  407. {
  408. struct bsd_db *db = state;
  409. int indx;
  410. if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)
  411. || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  412. || (BSD_NBITS(options[2]) != db->maxbits)
  413. || (decomp && db->lens == NULL))
  414. {
  415. return 0;
  416. }
  417. if (decomp)
  418. {
  419. indx = LAST;
  420. do
  421. {
  422. db->lens[indx] = 1;
  423. }
  424. while (indx-- > 0);
  425. }
  426. indx = db->hsize;
  427. while (indx-- != 0)
  428. {
  429. db->dict[indx].codem1 = BADCODEM1;
  430. db->dict[indx].cptr = 0;
  431. }
  432. db->unit = unit;
  433. db->mru = 0;
  434. #ifndef DEBUG
  435. if (debug)
  436. #endif
  437. db->debug = 1;
  438. bsd_reset(db);
  439. return 1;
  440. }
  441. static int bsd_comp_init (void *state, unsigned char *options,
  442. int opt_len, int unit, int opthdr, int debug)
  443. {
  444. return bsd_init (state, options, opt_len, unit, debug, 0);
  445. }
  446. static int bsd_decomp_init (void *state, unsigned char *options,
  447. int opt_len, int unit, int opthdr, int mru,
  448. int debug)
  449. {
  450. return bsd_init (state, options, opt_len, unit, debug, 1);
  451. }
  452. /*
  453. * Obtain pointers to the various structures in the compression tables
  454. */
  455. #define dict_ptrx(p,idx) &(p->dict[idx])
  456. #define lens_ptrx(p,idx) &(p->lens[idx])
  457. #ifdef DEBUG
  458. static unsigned short *lens_ptr(struct bsd_db *db, int idx)
  459. {
  460. if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
  461. {
  462. printk ("<9>ppp: lens_ptr(%d) > max\n", idx);
  463. idx = 0;
  464. }
  465. return lens_ptrx (db, idx);
  466. }
  467. static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
  468. {
  469. if ((unsigned int) idx >= (unsigned int) db->hsize)
  470. {
  471. printk ("<9>ppp: dict_ptr(%d) > max\n", idx);
  472. idx = 0;
  473. }
  474. return dict_ptrx (db, idx);
  475. }
  476. #else
  477. #define lens_ptr(db,idx) lens_ptrx(db,idx)
  478. #define dict_ptr(db,idx) dict_ptrx(db,idx)
  479. #endif
  480. /*
  481. * compress a packet
  482. *
  483. * The result of this function is the size of the compressed
  484. * packet. A zero is returned if the packet was not compressed
  485. * for some reason, such as the size being larger than uncompressed.
  486. *
  487. * One change from the BSD compress command is that when the
  488. * code size expands, we do not output a bunch of padding.
  489. */
  490. static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
  491. int isize, int osize)
  492. {
  493. struct bsd_db *db;
  494. int hshift;
  495. unsigned int max_ent;
  496. unsigned int n_bits;
  497. unsigned int bitno;
  498. unsigned long accm;
  499. int ent;
  500. unsigned long fcode;
  501. struct bsd_dict *dictp;
  502. unsigned char c;
  503. int hval;
  504. int disp;
  505. int ilen;
  506. int mxcode;
  507. unsigned char *wptr;
  508. int olen;
  509. #define PUTBYTE(v) \
  510. { \
  511. ++olen; \
  512. if (wptr) \
  513. { \
  514. *wptr++ = (unsigned char) (v); \
  515. if (olen >= osize) \
  516. { \
  517. wptr = NULL; \
  518. } \
  519. } \
  520. }
  521. #define OUTPUT(ent) \
  522. { \
  523. bitno -= n_bits; \
  524. accm |= ((ent) << bitno); \
  525. do \
  526. { \
  527. PUTBYTE(accm >> 24); \
  528. accm <<= 8; \
  529. bitno += 8; \
  530. } \
  531. while (bitno <= 24); \
  532. }
  533. /*
  534. * If the protocol is not in the range we're interested in,
  535. * just return without compressing the packet. If it is,
  536. * the protocol becomes the first byte to compress.
  537. */
  538. ent = PPP_PROTOCOL(rptr);
  539. if (ent < 0x21 || ent > 0xf9)
  540. {
  541. return 0;
  542. }
  543. db = (struct bsd_db *) state;
  544. hshift = db->hshift;
  545. max_ent = db->max_ent;
  546. n_bits = db->n_bits;
  547. bitno = 32;
  548. accm = 0;
  549. mxcode = MAXCODE (n_bits);
  550. /* Initialize the output pointers */
  551. wptr = obuf;
  552. olen = PPP_HDRLEN + BSD_OVHD;
  553. if (osize > isize)
  554. {
  555. osize = isize;
  556. }
  557. /* This is the PPP header information */
  558. if (wptr)
  559. {
  560. *wptr++ = PPP_ADDRESS(rptr);
  561. *wptr++ = PPP_CONTROL(rptr);
  562. *wptr++ = 0;
  563. *wptr++ = PPP_COMP;
  564. *wptr++ = db->seqno >> 8;
  565. *wptr++ = db->seqno;
  566. }
  567. /* Skip the input header */
  568. rptr += PPP_HDRLEN;
  569. isize -= PPP_HDRLEN;
  570. ilen = ++isize; /* Low byte of protocol is counted as input */
  571. while (--ilen > 0)
  572. {
  573. c = *rptr++;
  574. fcode = BSD_KEY (ent, c);
  575. hval = BSD_HASH (ent, c, hshift);
  576. dictp = dict_ptr (db, hval);
  577. /* Validate and then check the entry. */
  578. if (dictp->codem1 >= max_ent)
  579. {
  580. goto nomatch;
  581. }
  582. if (dictp->f.fcode == fcode)
  583. {
  584. ent = dictp->codem1 + 1;
  585. continue; /* found (prefix,suffix) */
  586. }
  587. /* continue probing until a match or invalid entry */
  588. disp = (hval == 0) ? 1 : hval;
  589. do
  590. {
  591. hval += disp;
  592. if (hval >= db->hsize)
  593. {
  594. hval -= db->hsize;
  595. }
  596. dictp = dict_ptr (db, hval);
  597. if (dictp->codem1 >= max_ent)
  598. {
  599. goto nomatch;
  600. }
  601. }
  602. while (dictp->f.fcode != fcode);
  603. ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */
  604. continue;
  605. nomatch:
  606. OUTPUT(ent); /* output the prefix */
  607. /* code -> hashtable */
  608. if (max_ent < db->maxmaxcode)
  609. {
  610. struct bsd_dict *dictp2;
  611. struct bsd_dict *dictp3;
  612. int indx;
  613. /* expand code size if needed */
  614. if (max_ent >= mxcode)
  615. {
  616. db->n_bits = ++n_bits;
  617. mxcode = MAXCODE (n_bits);
  618. }
  619. /* Invalidate old hash table entry using
  620. * this code, and then take it over.
  621. */
  622. dictp2 = dict_ptr (db, max_ent + 1);
  623. indx = dictp2->cptr;
  624. dictp3 = dict_ptr (db, indx);
  625. if (dictp3->codem1 == max_ent)
  626. {
  627. dictp3->codem1 = BADCODEM1;
  628. }
  629. dictp2->cptr = hval;
  630. dictp->codem1 = max_ent;
  631. dictp->f.fcode = fcode;
  632. db->max_ent = ++max_ent;
  633. if (db->lens)
  634. {
  635. unsigned short *len1 = lens_ptr (db, max_ent);
  636. unsigned short *len2 = lens_ptr (db, ent);
  637. *len1 = *len2 + 1;
  638. }
  639. }
  640. ent = c;
  641. }
  642. OUTPUT(ent); /* output the last code */
  643. db->bytes_out += olen - PPP_HDRLEN - BSD_OVHD;
  644. db->uncomp_bytes += isize;
  645. db->in_count += isize;
  646. ++db->uncomp_count;
  647. ++db->seqno;
  648. if (bitno < 32)
  649. {
  650. ++db->bytes_out; /* must be set before calling bsd_check */
  651. }
  652. /*
  653. * Generate the clear command if needed
  654. */
  655. if (bsd_check(db))
  656. {
  657. OUTPUT (CLEAR);
  658. }
  659. /*
  660. * Pad dribble bits of last code with ones.
  661. * Do not emit a completely useless byte of ones.
  662. */
  663. if (bitno != 32)
  664. {
  665. PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  666. }
  667. /*
  668. * Increase code size if we would have without the packet
  669. * boundary because the decompressor will do so.
  670. */
  671. if (max_ent >= mxcode && max_ent < db->maxmaxcode)
  672. {
  673. db->n_bits++;
  674. }
  675. /* If output length is too large then this is an incomplete frame. */
  676. if (wptr == NULL)
  677. {
  678. ++db->incomp_count;
  679. db->incomp_bytes += isize;
  680. olen = 0;
  681. }
  682. else /* Count the number of compressed frames */
  683. {
  684. ++db->comp_count;
  685. db->comp_bytes += olen;
  686. }
  687. /* Return the resulting output length */
  688. return olen;
  689. #undef OUTPUT
  690. #undef PUTBYTE
  691. }
  692. /*
  693. * Update the "BSD Compress" dictionary on the receiver for
  694. * incompressible data by pretending to compress the incoming data.
  695. */
  696. static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
  697. {
  698. (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
  699. }
  700. /*
  701. * Decompress "BSD Compress".
  702. *
  703. * Because of patent problems, we return DECOMP_ERROR for errors
  704. * found by inspecting the input data and for system problems, but
  705. * DECOMP_FATALERROR for any errors which could possibly be said to
  706. * be being detected "after" decompression. For DECOMP_ERROR,
  707. * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
  708. * infringing a patent of Motorola's if we do, so we take CCP down
  709. * instead.
  710. *
  711. * Given that the frame has the correct sequence number and a good FCS,
  712. * errors such as invalid codes in the input most likely indicate a
  713. * bug, so we return DECOMP_FATALERROR for them in order to turn off
  714. * compression, even though they are detected by inspecting the input.
  715. */
  716. static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
  717. unsigned char *obuf, int osize)
  718. {
  719. struct bsd_db *db;
  720. unsigned int max_ent;
  721. unsigned long accm;
  722. unsigned int bitno; /* 1st valid bit in accm */
  723. unsigned int n_bits;
  724. unsigned int tgtbitno; /* bitno when we have a code */
  725. struct bsd_dict *dictp;
  726. int explen;
  727. int seq;
  728. unsigned int incode;
  729. unsigned int oldcode;
  730. unsigned int finchar;
  731. unsigned char *p;
  732. unsigned char *wptr;
  733. int adrs;
  734. int ctrl;
  735. int ilen;
  736. int codelen;
  737. int extra;
  738. db = (struct bsd_db *) state;
  739. max_ent = db->max_ent;
  740. accm = 0;
  741. bitno = 32; /* 1st valid bit in accm */
  742. n_bits = db->n_bits;
  743. tgtbitno = 32 - n_bits; /* bitno when we have a code */
  744. /*
  745. * Save the address/control from the PPP header
  746. * and then get the sequence number.
  747. */
  748. adrs = PPP_ADDRESS (ibuf);
  749. ctrl = PPP_CONTROL (ibuf);
  750. seq = (ibuf[4] << 8) + ibuf[5];
  751. ibuf += (PPP_HDRLEN + 2);
  752. ilen = isize - (PPP_HDRLEN + 2);
  753. /*
  754. * Check the sequence number and give up if it differs from
  755. * the value we're expecting.
  756. */
  757. if (seq != db->seqno)
  758. {
  759. if (db->debug)
  760. {
  761. printk("bsd_decomp%d: bad sequence # %d, expected %d\n",
  762. db->unit, seq, db->seqno - 1);
  763. }
  764. return DECOMP_ERROR;
  765. }
  766. ++db->seqno;
  767. db->bytes_out += ilen;
  768. /*
  769. * Fill in the ppp header, but not the last byte of the protocol
  770. * (that comes from the decompressed data).
  771. */
  772. wptr = obuf;
  773. *wptr++ = adrs;
  774. *wptr++ = ctrl;
  775. *wptr++ = 0;
  776. oldcode = CLEAR;
  777. explen = 3;
  778. /*
  779. * Keep the checkpoint correctly so that incompressible packets
  780. * clear the dictionary at the proper times.
  781. */
  782. for (;;)
  783. {
  784. if (ilen-- <= 0)
  785. {
  786. db->in_count += (explen - 3); /* don't count the header */
  787. break;
  788. }
  789. /*
  790. * Accumulate bytes until we have a complete code.
  791. * Then get the next code, relying on the 32-bit,
  792. * unsigned accm to mask the result.
  793. */
  794. bitno -= 8;
  795. accm |= *ibuf++ << bitno;
  796. if (tgtbitno < bitno)
  797. {
  798. continue;
  799. }
  800. incode = accm >> tgtbitno;
  801. accm <<= n_bits;
  802. bitno += n_bits;
  803. /*
  804. * The dictionary must only be cleared at the end of a packet.
  805. */
  806. if (incode == CLEAR)
  807. {
  808. if (ilen > 0)
  809. {
  810. if (db->debug)
  811. {
  812. printk("bsd_decomp%d: bad CLEAR\n", db->unit);
  813. }
  814. return DECOMP_FATALERROR; /* probably a bug */
  815. }
  816. bsd_clear(db);
  817. break;
  818. }
  819. if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
  820. || (incode > max_ent && oldcode == CLEAR))
  821. {
  822. if (db->debug)
  823. {
  824. printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  825. db->unit, incode, oldcode);
  826. printk("max_ent=0x%x explen=%d seqno=%d\n",
  827. max_ent, explen, db->seqno);
  828. }
  829. return DECOMP_FATALERROR; /* probably a bug */
  830. }
  831. /* Special case for KwKwK string. */
  832. if (incode > max_ent)
  833. {
  834. finchar = oldcode;
  835. extra = 1;
  836. }
  837. else
  838. {
  839. finchar = incode;
  840. extra = 0;
  841. }
  842. codelen = *(lens_ptr (db, finchar));
  843. explen += codelen + extra;
  844. if (explen > osize)
  845. {
  846. if (db->debug)
  847. {
  848. printk("bsd_decomp%d: ran out of mru\n", db->unit);
  849. #ifdef DEBUG
  850. printk(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
  851. ilen, finchar, codelen, explen);
  852. #endif
  853. }
  854. return DECOMP_FATALERROR;
  855. }
  856. /*
  857. * Decode this code and install it in the decompressed buffer.
  858. */
  859. wptr += codelen;
  860. p = wptr;
  861. while (finchar > LAST)
  862. {
  863. struct bsd_dict *dictp2 = dict_ptr (db, finchar);
  864. dictp = dict_ptr (db, dictp2->cptr);
  865. #ifdef DEBUG
  866. if (--codelen <= 0 || dictp->codem1 != finchar-1)
  867. {
  868. if (codelen <= 0)
  869. {
  870. printk("bsd_decomp%d: fell off end of chain ", db->unit);
  871. printk("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
  872. incode, finchar, dictp2->cptr, max_ent);
  873. }
  874. else
  875. {
  876. if (dictp->codem1 != finchar-1)
  877. {
  878. printk("bsd_decomp%d: bad code chain 0x%x "
  879. "finchar=0x%x ",
  880. db->unit, incode, finchar);
  881. printk("oldcode=0x%x cptr=0x%x codem1=0x%x\n",
  882. oldcode, dictp2->cptr, dictp->codem1);
  883. }
  884. }
  885. return DECOMP_FATALERROR;
  886. }
  887. #endif
  888. *--p = dictp->f.hs.suffix;
  889. finchar = dictp->f.hs.prefix;
  890. }
  891. *--p = finchar;
  892. #ifdef DEBUG
  893. if (--codelen != 0)
  894. {
  895. printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
  896. db->unit, codelen, incode, max_ent);
  897. }
  898. #endif
  899. if (extra) /* the KwKwK case again */
  900. {
  901. *wptr++ = finchar;
  902. }
  903. /*
  904. * If not first code in a packet, and
  905. * if not out of code space, then allocate a new code.
  906. *
  907. * Keep the hash table correct so it can be used
  908. * with uncompressed packets.
  909. */
  910. if (oldcode != CLEAR && max_ent < db->maxmaxcode)
  911. {
  912. struct bsd_dict *dictp2, *dictp3;
  913. unsigned short *lens1, *lens2;
  914. unsigned long fcode;
  915. int hval, disp, indx;
  916. fcode = BSD_KEY(oldcode,finchar);
  917. hval = BSD_HASH(oldcode,finchar,db->hshift);
  918. dictp = dict_ptr (db, hval);
  919. /* look for a free hash table entry */
  920. if (dictp->codem1 < max_ent)
  921. {
  922. disp = (hval == 0) ? 1 : hval;
  923. do
  924. {
  925. hval += disp;
  926. if (hval >= db->hsize)
  927. {
  928. hval -= db->hsize;
  929. }
  930. dictp = dict_ptr (db, hval);
  931. }
  932. while (dictp->codem1 < max_ent);
  933. }
  934. /*
  935. * Invalidate previous hash table entry
  936. * assigned this code, and then take it over
  937. */
  938. dictp2 = dict_ptr (db, max_ent + 1);
  939. indx = dictp2->cptr;
  940. dictp3 = dict_ptr (db, indx);
  941. if (dictp3->codem1 == max_ent)
  942. {
  943. dictp3->codem1 = BADCODEM1;
  944. }
  945. dictp2->cptr = hval;
  946. dictp->codem1 = max_ent;
  947. dictp->f.fcode = fcode;
  948. db->max_ent = ++max_ent;
  949. /* Update the length of this string. */
  950. lens1 = lens_ptr (db, max_ent);
  951. lens2 = lens_ptr (db, oldcode);
  952. *lens1 = *lens2 + 1;
  953. /* Expand code size if needed. */
  954. if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  955. {
  956. db->n_bits = ++n_bits;
  957. tgtbitno = 32-n_bits;
  958. }
  959. }
  960. oldcode = incode;
  961. }
  962. ++db->comp_count;
  963. ++db->uncomp_count;
  964. db->comp_bytes += isize - BSD_OVHD - PPP_HDRLEN;
  965. db->uncomp_bytes += explen;
  966. if (bsd_check(db))
  967. {
  968. if (db->debug)
  969. {
  970. printk("bsd_decomp%d: peer should have cleared dictionary on %d\n",
  971. db->unit, db->seqno - 1);
  972. }
  973. }
  974. return explen;
  975. }
  976. /*************************************************************
  977. * Table of addresses for the BSD compression module
  978. *************************************************************/
  979. static struct compressor ppp_bsd_compress = {
  980. .compress_proto = CI_BSD_COMPRESS,
  981. .comp_alloc = bsd_comp_alloc,
  982. .comp_free = bsd_free,
  983. .comp_init = bsd_comp_init,
  984. .comp_reset = bsd_reset,
  985. .compress = bsd_compress,
  986. .comp_stat = bsd_comp_stats,
  987. .decomp_alloc = bsd_decomp_alloc,
  988. .decomp_free = bsd_free,
  989. .decomp_init = bsd_decomp_init,
  990. .decomp_reset = bsd_reset,
  991. .decompress = bsd_decompress,
  992. .incomp = bsd_incomp,
  993. .decomp_stat = bsd_comp_stats,
  994. .owner = THIS_MODULE
  995. };
  996. /*************************************************************
  997. * Module support routines
  998. *************************************************************/
  999. static int __init bsdcomp_init(void)
  1000. {
  1001. int answer = ppp_register_compressor(&ppp_bsd_compress);
  1002. if (answer == 0)
  1003. printk(KERN_INFO "PPP BSD Compression module registered\n");
  1004. return answer;
  1005. }
  1006. static void __exit bsdcomp_cleanup(void)
  1007. {
  1008. ppp_unregister_compressor(&ppp_bsd_compress);
  1009. }
  1010. module_init(bsdcomp_init);
  1011. module_exit(bsdcomp_cleanup);
  1012. MODULE_LICENSE("Dual BSD/GPL");
  1013. MODULE_ALIAS("ppp-compress-" __stringify(CI_BSD_COMPRESS));