bsd_comp.c 29 KB

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