bsd_comp.c 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179
  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 = (struct bsd_db *) state;
  285. if (db)
  286. {
  287. /*
  288. * Release the dictionary
  289. */
  290. if (db->dict)
  291. {
  292. vfree (db->dict);
  293. db->dict = NULL;
  294. }
  295. /*
  296. * Release the string buffer
  297. */
  298. if (db->lens)
  299. {
  300. vfree (db->lens);
  301. db->lens = NULL;
  302. }
  303. /*
  304. * Finally release the structure itself.
  305. */
  306. kfree (db);
  307. }
  308. }
  309. /*
  310. * Allocate space for a (de) compressor.
  311. */
  312. static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
  313. {
  314. int bits;
  315. unsigned int hsize, hshift, maxmaxcode;
  316. struct bsd_db *db;
  317. if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
  318. || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  319. {
  320. return NULL;
  321. }
  322. bits = BSD_NBITS(options[2]);
  323. switch (bits)
  324. {
  325. case 9: /* needs 82152 for both directions */
  326. case 10: /* needs 84144 */
  327. case 11: /* needs 88240 */
  328. case 12: /* needs 96432 */
  329. hsize = 5003;
  330. hshift = 4;
  331. break;
  332. case 13: /* needs 176784 */
  333. hsize = 9001;
  334. hshift = 5;
  335. break;
  336. case 14: /* needs 353744 */
  337. hsize = 18013;
  338. hshift = 6;
  339. break;
  340. case 15: /* needs 691440 */
  341. hsize = 35023;
  342. hshift = 7;
  343. break;
  344. case 16: /* needs 1366160--far too much, */
  345. /* hsize = 69001; */ /* and 69001 is too big for cptr */
  346. /* hshift = 8; */ /* in struct bsd_db */
  347. /* break; */
  348. default:
  349. return NULL;
  350. }
  351. /*
  352. * Allocate the main control structure for this instance.
  353. */
  354. maxmaxcode = MAXCODE(bits);
  355. db = (struct bsd_db *) kmalloc (sizeof (struct bsd_db),
  356. GFP_KERNEL);
  357. if (!db)
  358. {
  359. return NULL;
  360. }
  361. memset (db, 0, sizeof(struct bsd_db));
  362. /*
  363. * Allocate space for the dictionary. This may be more than one page in
  364. * length.
  365. */
  366. db->dict = (struct bsd_dict *) vmalloc (hsize *
  367. sizeof (struct bsd_dict));
  368. if (!db->dict)
  369. {
  370. bsd_free (db);
  371. return NULL;
  372. }
  373. /*
  374. * If this is the compression buffer then there is no length data.
  375. */
  376. if (!decomp)
  377. {
  378. db->lens = NULL;
  379. }
  380. /*
  381. * For decompression, the length information is needed as well.
  382. */
  383. else
  384. {
  385. db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *
  386. sizeof (db->lens[0]));
  387. if (!db->lens)
  388. {
  389. bsd_free (db);
  390. return (NULL);
  391. }
  392. }
  393. /*
  394. * Initialize the data information for the compression code
  395. */
  396. db->totlen = sizeof (struct bsd_db) +
  397. (sizeof (struct bsd_dict) * hsize);
  398. db->hsize = hsize;
  399. db->hshift = hshift;
  400. db->maxmaxcode = maxmaxcode;
  401. db->maxbits = bits;
  402. return (void *) db;
  403. }
  404. static void *bsd_comp_alloc (unsigned char *options, int opt_len)
  405. {
  406. return bsd_alloc (options, opt_len, 0);
  407. }
  408. static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
  409. {
  410. return bsd_alloc (options, opt_len, 1);
  411. }
  412. /*
  413. * Initialize the database.
  414. */
  415. static int bsd_init (void *state, unsigned char *options,
  416. int opt_len, int unit, int debug, int decomp)
  417. {
  418. struct bsd_db *db = state;
  419. int indx;
  420. if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)
  421. || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  422. || (BSD_NBITS(options[2]) != db->maxbits)
  423. || (decomp && db->lens == NULL))
  424. {
  425. return 0;
  426. }
  427. if (decomp)
  428. {
  429. indx = LAST;
  430. do
  431. {
  432. db->lens[indx] = 1;
  433. }
  434. while (indx-- > 0);
  435. }
  436. indx = db->hsize;
  437. while (indx-- != 0)
  438. {
  439. db->dict[indx].codem1 = BADCODEM1;
  440. db->dict[indx].cptr = 0;
  441. }
  442. db->unit = unit;
  443. db->mru = 0;
  444. #ifndef DEBUG
  445. if (debug)
  446. #endif
  447. db->debug = 1;
  448. bsd_reset(db);
  449. return 1;
  450. }
  451. static int bsd_comp_init (void *state, unsigned char *options,
  452. int opt_len, int unit, int opthdr, int debug)
  453. {
  454. return bsd_init (state, options, opt_len, unit, debug, 0);
  455. }
  456. static int bsd_decomp_init (void *state, unsigned char *options,
  457. int opt_len, int unit, int opthdr, int mru,
  458. int debug)
  459. {
  460. return bsd_init (state, options, opt_len, unit, debug, 1);
  461. }
  462. /*
  463. * Obtain pointers to the various structures in the compression tables
  464. */
  465. #define dict_ptrx(p,idx) &(p->dict[idx])
  466. #define lens_ptrx(p,idx) &(p->lens[idx])
  467. #ifdef DEBUG
  468. static unsigned short *lens_ptr(struct bsd_db *db, int idx)
  469. {
  470. if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
  471. {
  472. printk ("<9>ppp: lens_ptr(%d) > max\n", idx);
  473. idx = 0;
  474. }
  475. return lens_ptrx (db, idx);
  476. }
  477. static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
  478. {
  479. if ((unsigned int) idx >= (unsigned int) db->hsize)
  480. {
  481. printk ("<9>ppp: dict_ptr(%d) > max\n", idx);
  482. idx = 0;
  483. }
  484. return dict_ptrx (db, idx);
  485. }
  486. #else
  487. #define lens_ptr(db,idx) lens_ptrx(db,idx)
  488. #define dict_ptr(db,idx) dict_ptrx(db,idx)
  489. #endif
  490. /*
  491. * compress a packet
  492. *
  493. * The result of this function is the size of the compressed
  494. * packet. A zero is returned if the packet was not compressed
  495. * for some reason, such as the size being larger than uncompressed.
  496. *
  497. * One change from the BSD compress command is that when the
  498. * code size expands, we do not output a bunch of padding.
  499. */
  500. static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
  501. int isize, int osize)
  502. {
  503. struct bsd_db *db;
  504. int hshift;
  505. unsigned int max_ent;
  506. unsigned int n_bits;
  507. unsigned int bitno;
  508. unsigned long accm;
  509. int ent;
  510. unsigned long fcode;
  511. struct bsd_dict *dictp;
  512. unsigned char c;
  513. int hval;
  514. int disp;
  515. int ilen;
  516. int mxcode;
  517. unsigned char *wptr;
  518. int olen;
  519. #define PUTBYTE(v) \
  520. { \
  521. ++olen; \
  522. if (wptr) \
  523. { \
  524. *wptr++ = (unsigned char) (v); \
  525. if (olen >= osize) \
  526. { \
  527. wptr = NULL; \
  528. } \
  529. } \
  530. }
  531. #define OUTPUT(ent) \
  532. { \
  533. bitno -= n_bits; \
  534. accm |= ((ent) << bitno); \
  535. do \
  536. { \
  537. PUTBYTE(accm >> 24); \
  538. accm <<= 8; \
  539. bitno += 8; \
  540. } \
  541. while (bitno <= 24); \
  542. }
  543. /*
  544. * If the protocol is not in the range we're interested in,
  545. * just return without compressing the packet. If it is,
  546. * the protocol becomes the first byte to compress.
  547. */
  548. ent = PPP_PROTOCOL(rptr);
  549. if (ent < 0x21 || ent > 0xf9)
  550. {
  551. return 0;
  552. }
  553. db = (struct bsd_db *) state;
  554. hshift = db->hshift;
  555. max_ent = db->max_ent;
  556. n_bits = db->n_bits;
  557. bitno = 32;
  558. accm = 0;
  559. mxcode = MAXCODE (n_bits);
  560. /* Initialize the output pointers */
  561. wptr = obuf;
  562. olen = PPP_HDRLEN + BSD_OVHD;
  563. if (osize > isize)
  564. {
  565. osize = isize;
  566. }
  567. /* This is the PPP header information */
  568. if (wptr)
  569. {
  570. *wptr++ = PPP_ADDRESS(rptr);
  571. *wptr++ = PPP_CONTROL(rptr);
  572. *wptr++ = 0;
  573. *wptr++ = PPP_COMP;
  574. *wptr++ = db->seqno >> 8;
  575. *wptr++ = db->seqno;
  576. }
  577. /* Skip the input header */
  578. rptr += PPP_HDRLEN;
  579. isize -= PPP_HDRLEN;
  580. ilen = ++isize; /* Low byte of protocol is counted as input */
  581. while (--ilen > 0)
  582. {
  583. c = *rptr++;
  584. fcode = BSD_KEY (ent, c);
  585. hval = BSD_HASH (ent, c, hshift);
  586. dictp = dict_ptr (db, hval);
  587. /* Validate and then check the entry. */
  588. if (dictp->codem1 >= max_ent)
  589. {
  590. goto nomatch;
  591. }
  592. if (dictp->f.fcode == fcode)
  593. {
  594. ent = dictp->codem1 + 1;
  595. continue; /* found (prefix,suffix) */
  596. }
  597. /* continue probing until a match or invalid entry */
  598. disp = (hval == 0) ? 1 : hval;
  599. do
  600. {
  601. hval += disp;
  602. if (hval >= db->hsize)
  603. {
  604. hval -= db->hsize;
  605. }
  606. dictp = dict_ptr (db, hval);
  607. if (dictp->codem1 >= max_ent)
  608. {
  609. goto nomatch;
  610. }
  611. }
  612. while (dictp->f.fcode != fcode);
  613. ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */
  614. continue;
  615. nomatch:
  616. OUTPUT(ent); /* output the prefix */
  617. /* code -> hashtable */
  618. if (max_ent < db->maxmaxcode)
  619. {
  620. struct bsd_dict *dictp2;
  621. struct bsd_dict *dictp3;
  622. int indx;
  623. /* expand code size if needed */
  624. if (max_ent >= mxcode)
  625. {
  626. db->n_bits = ++n_bits;
  627. mxcode = MAXCODE (n_bits);
  628. }
  629. /* Invalidate old hash table entry using
  630. * this code, and then take it over.
  631. */
  632. dictp2 = dict_ptr (db, max_ent + 1);
  633. indx = dictp2->cptr;
  634. dictp3 = dict_ptr (db, indx);
  635. if (dictp3->codem1 == max_ent)
  636. {
  637. dictp3->codem1 = BADCODEM1;
  638. }
  639. dictp2->cptr = hval;
  640. dictp->codem1 = max_ent;
  641. dictp->f.fcode = fcode;
  642. db->max_ent = ++max_ent;
  643. if (db->lens)
  644. {
  645. unsigned short *len1 = lens_ptr (db, max_ent);
  646. unsigned short *len2 = lens_ptr (db, ent);
  647. *len1 = *len2 + 1;
  648. }
  649. }
  650. ent = c;
  651. }
  652. OUTPUT(ent); /* output the last code */
  653. db->bytes_out += olen - PPP_HDRLEN - BSD_OVHD;
  654. db->uncomp_bytes += isize;
  655. db->in_count += isize;
  656. ++db->uncomp_count;
  657. ++db->seqno;
  658. if (bitno < 32)
  659. {
  660. ++db->bytes_out; /* must be set before calling bsd_check */
  661. }
  662. /*
  663. * Generate the clear command if needed
  664. */
  665. if (bsd_check(db))
  666. {
  667. OUTPUT (CLEAR);
  668. }
  669. /*
  670. * Pad dribble bits of last code with ones.
  671. * Do not emit a completely useless byte of ones.
  672. */
  673. if (bitno != 32)
  674. {
  675. PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  676. }
  677. /*
  678. * Increase code size if we would have without the packet
  679. * boundary because the decompressor will do so.
  680. */
  681. if (max_ent >= mxcode && max_ent < db->maxmaxcode)
  682. {
  683. db->n_bits++;
  684. }
  685. /* If output length is too large then this is an incomplete frame. */
  686. if (wptr == NULL)
  687. {
  688. ++db->incomp_count;
  689. db->incomp_bytes += isize;
  690. olen = 0;
  691. }
  692. else /* Count the number of compressed frames */
  693. {
  694. ++db->comp_count;
  695. db->comp_bytes += olen;
  696. }
  697. /* Return the resulting output length */
  698. return olen;
  699. #undef OUTPUT
  700. #undef PUTBYTE
  701. }
  702. /*
  703. * Update the "BSD Compress" dictionary on the receiver for
  704. * incompressible data by pretending to compress the incoming data.
  705. */
  706. static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
  707. {
  708. (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
  709. }
  710. /*
  711. * Decompress "BSD Compress".
  712. *
  713. * Because of patent problems, we return DECOMP_ERROR for errors
  714. * found by inspecting the input data and for system problems, but
  715. * DECOMP_FATALERROR for any errors which could possibly be said to
  716. * be being detected "after" decompression. For DECOMP_ERROR,
  717. * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
  718. * infringing a patent of Motorola's if we do, so we take CCP down
  719. * instead.
  720. *
  721. * Given that the frame has the correct sequence number and a good FCS,
  722. * errors such as invalid codes in the input most likely indicate a
  723. * bug, so we return DECOMP_FATALERROR for them in order to turn off
  724. * compression, even though they are detected by inspecting the input.
  725. */
  726. static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
  727. unsigned char *obuf, int osize)
  728. {
  729. struct bsd_db *db;
  730. unsigned int max_ent;
  731. unsigned long accm;
  732. unsigned int bitno; /* 1st valid bit in accm */
  733. unsigned int n_bits;
  734. unsigned int tgtbitno; /* bitno when we have a code */
  735. struct bsd_dict *dictp;
  736. int explen;
  737. int seq;
  738. unsigned int incode;
  739. unsigned int oldcode;
  740. unsigned int finchar;
  741. unsigned char *p;
  742. unsigned char *wptr;
  743. int adrs;
  744. int ctrl;
  745. int ilen;
  746. int codelen;
  747. int extra;
  748. db = (struct bsd_db *) state;
  749. max_ent = db->max_ent;
  750. accm = 0;
  751. bitno = 32; /* 1st valid bit in accm */
  752. n_bits = db->n_bits;
  753. tgtbitno = 32 - n_bits; /* bitno when we have a code */
  754. /*
  755. * Save the address/control from the PPP header
  756. * and then get the sequence number.
  757. */
  758. adrs = PPP_ADDRESS (ibuf);
  759. ctrl = PPP_CONTROL (ibuf);
  760. seq = (ibuf[4] << 8) + ibuf[5];
  761. ibuf += (PPP_HDRLEN + 2);
  762. ilen = isize - (PPP_HDRLEN + 2);
  763. /*
  764. * Check the sequence number and give up if it differs from
  765. * the value we're expecting.
  766. */
  767. if (seq != db->seqno)
  768. {
  769. if (db->debug)
  770. {
  771. printk("bsd_decomp%d: bad sequence # %d, expected %d\n",
  772. db->unit, seq, db->seqno - 1);
  773. }
  774. return DECOMP_ERROR;
  775. }
  776. ++db->seqno;
  777. db->bytes_out += ilen;
  778. /*
  779. * Fill in the ppp header, but not the last byte of the protocol
  780. * (that comes from the decompressed data).
  781. */
  782. wptr = obuf;
  783. *wptr++ = adrs;
  784. *wptr++ = ctrl;
  785. *wptr++ = 0;
  786. oldcode = CLEAR;
  787. explen = 3;
  788. /*
  789. * Keep the checkpoint correctly so that incompressible packets
  790. * clear the dictionary at the proper times.
  791. */
  792. for (;;)
  793. {
  794. if (ilen-- <= 0)
  795. {
  796. db->in_count += (explen - 3); /* don't count the header */
  797. break;
  798. }
  799. /*
  800. * Accumulate bytes until we have a complete code.
  801. * Then get the next code, relying on the 32-bit,
  802. * unsigned accm to mask the result.
  803. */
  804. bitno -= 8;
  805. accm |= *ibuf++ << bitno;
  806. if (tgtbitno < bitno)
  807. {
  808. continue;
  809. }
  810. incode = accm >> tgtbitno;
  811. accm <<= n_bits;
  812. bitno += n_bits;
  813. /*
  814. * The dictionary must only be cleared at the end of a packet.
  815. */
  816. if (incode == CLEAR)
  817. {
  818. if (ilen > 0)
  819. {
  820. if (db->debug)
  821. {
  822. printk("bsd_decomp%d: bad CLEAR\n", db->unit);
  823. }
  824. return DECOMP_FATALERROR; /* probably a bug */
  825. }
  826. bsd_clear(db);
  827. break;
  828. }
  829. if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
  830. || (incode > max_ent && oldcode == CLEAR))
  831. {
  832. if (db->debug)
  833. {
  834. printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  835. db->unit, incode, oldcode);
  836. printk("max_ent=0x%x explen=%d seqno=%d\n",
  837. max_ent, explen, db->seqno);
  838. }
  839. return DECOMP_FATALERROR; /* probably a bug */
  840. }
  841. /* Special case for KwKwK string. */
  842. if (incode > max_ent)
  843. {
  844. finchar = oldcode;
  845. extra = 1;
  846. }
  847. else
  848. {
  849. finchar = incode;
  850. extra = 0;
  851. }
  852. codelen = *(lens_ptr (db, finchar));
  853. explen += codelen + extra;
  854. if (explen > osize)
  855. {
  856. if (db->debug)
  857. {
  858. printk("bsd_decomp%d: ran out of mru\n", db->unit);
  859. #ifdef DEBUG
  860. printk(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
  861. ilen, finchar, codelen, explen);
  862. #endif
  863. }
  864. return DECOMP_FATALERROR;
  865. }
  866. /*
  867. * Decode this code and install it in the decompressed buffer.
  868. */
  869. wptr += codelen;
  870. p = wptr;
  871. while (finchar > LAST)
  872. {
  873. struct bsd_dict *dictp2 = dict_ptr (db, finchar);
  874. dictp = dict_ptr (db, dictp2->cptr);
  875. #ifdef DEBUG
  876. if (--codelen <= 0 || dictp->codem1 != finchar-1)
  877. {
  878. if (codelen <= 0)
  879. {
  880. printk("bsd_decomp%d: fell off end of chain ", db->unit);
  881. printk("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
  882. incode, finchar, dictp2->cptr, max_ent);
  883. }
  884. else
  885. {
  886. if (dictp->codem1 != finchar-1)
  887. {
  888. printk("bsd_decomp%d: bad code chain 0x%x "
  889. "finchar=0x%x ",
  890. db->unit, incode, finchar);
  891. printk("oldcode=0x%x cptr=0x%x codem1=0x%x\n",
  892. oldcode, dictp2->cptr, dictp->codem1);
  893. }
  894. }
  895. return DECOMP_FATALERROR;
  896. }
  897. #endif
  898. *--p = dictp->f.hs.suffix;
  899. finchar = dictp->f.hs.prefix;
  900. }
  901. *--p = finchar;
  902. #ifdef DEBUG
  903. if (--codelen != 0)
  904. {
  905. printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
  906. db->unit, codelen, incode, max_ent);
  907. }
  908. #endif
  909. if (extra) /* the KwKwK case again */
  910. {
  911. *wptr++ = finchar;
  912. }
  913. /*
  914. * If not first code in a packet, and
  915. * if not out of code space, then allocate a new code.
  916. *
  917. * Keep the hash table correct so it can be used
  918. * with uncompressed packets.
  919. */
  920. if (oldcode != CLEAR && max_ent < db->maxmaxcode)
  921. {
  922. struct bsd_dict *dictp2, *dictp3;
  923. unsigned short *lens1, *lens2;
  924. unsigned long fcode;
  925. int hval, disp, indx;
  926. fcode = BSD_KEY(oldcode,finchar);
  927. hval = BSD_HASH(oldcode,finchar,db->hshift);
  928. dictp = dict_ptr (db, hval);
  929. /* look for a free hash table entry */
  930. if (dictp->codem1 < max_ent)
  931. {
  932. disp = (hval == 0) ? 1 : hval;
  933. do
  934. {
  935. hval += disp;
  936. if (hval >= db->hsize)
  937. {
  938. hval -= db->hsize;
  939. }
  940. dictp = dict_ptr (db, hval);
  941. }
  942. while (dictp->codem1 < max_ent);
  943. }
  944. /*
  945. * Invalidate previous hash table entry
  946. * assigned this code, and then take it over
  947. */
  948. dictp2 = dict_ptr (db, max_ent + 1);
  949. indx = dictp2->cptr;
  950. dictp3 = dict_ptr (db, indx);
  951. if (dictp3->codem1 == max_ent)
  952. {
  953. dictp3->codem1 = BADCODEM1;
  954. }
  955. dictp2->cptr = hval;
  956. dictp->codem1 = max_ent;
  957. dictp->f.fcode = fcode;
  958. db->max_ent = ++max_ent;
  959. /* Update the length of this string. */
  960. lens1 = lens_ptr (db, max_ent);
  961. lens2 = lens_ptr (db, oldcode);
  962. *lens1 = *lens2 + 1;
  963. /* Expand code size if needed. */
  964. if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  965. {
  966. db->n_bits = ++n_bits;
  967. tgtbitno = 32-n_bits;
  968. }
  969. }
  970. oldcode = incode;
  971. }
  972. ++db->comp_count;
  973. ++db->uncomp_count;
  974. db->comp_bytes += isize - BSD_OVHD - PPP_HDRLEN;
  975. db->uncomp_bytes += explen;
  976. if (bsd_check(db))
  977. {
  978. if (db->debug)
  979. {
  980. printk("bsd_decomp%d: peer should have cleared dictionary on %d\n",
  981. db->unit, db->seqno - 1);
  982. }
  983. }
  984. return explen;
  985. }
  986. /*************************************************************
  987. * Table of addresses for the BSD compression module
  988. *************************************************************/
  989. static struct compressor ppp_bsd_compress = {
  990. .compress_proto = CI_BSD_COMPRESS,
  991. .comp_alloc = bsd_comp_alloc,
  992. .comp_free = bsd_free,
  993. .comp_init = bsd_comp_init,
  994. .comp_reset = bsd_reset,
  995. .compress = bsd_compress,
  996. .comp_stat = bsd_comp_stats,
  997. .decomp_alloc = bsd_decomp_alloc,
  998. .decomp_free = bsd_free,
  999. .decomp_init = bsd_decomp_init,
  1000. .decomp_reset = bsd_reset,
  1001. .decompress = bsd_decompress,
  1002. .incomp = bsd_incomp,
  1003. .decomp_stat = bsd_comp_stats,
  1004. .owner = THIS_MODULE
  1005. };
  1006. /*************************************************************
  1007. * Module support routines
  1008. *************************************************************/
  1009. static int __init bsdcomp_init(void)
  1010. {
  1011. int answer = ppp_register_compressor(&ppp_bsd_compress);
  1012. if (answer == 0)
  1013. printk(KERN_INFO "PPP BSD Compression module registered\n");
  1014. return answer;
  1015. }
  1016. static void __exit bsdcomp_cleanup(void)
  1017. {
  1018. ppp_unregister_compressor(&ppp_bsd_compress);
  1019. }
  1020. module_init(bsdcomp_init);
  1021. module_exit(bsdcomp_cleanup);
  1022. MODULE_LICENSE("Dual BSD/GPL");
  1023. MODULE_ALIAS("ppp-compress-" __stringify(CI_BSD_COMPRESS));