SHARE
TWEET

Untitled

a guest Nov 18th, 2019 109 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. diff --git a/.gitignore b/.gitignore
  2. new file mode 100644
  3. index 0000000..6fc4f0c
  4. --- /dev/null
  5. +++ b/.gitignore
  6. @@ -0,0 +1,2 @@
  7. +tmp/
  8. +bin/
  9. \ No newline at end of file
  10. diff --git a/Makefile b/Makefile
  11. index 72310a6..aec0462 100644
  12. --- a/Makefile
  13. +++ b/Makefile
  14. @@ -1,21 +1,34 @@
  15. -lzwarc: arc.o lzw.o huffman.o futils.o diter.o queue.o
  16. -   gcc -o lzwarc arc.o lzw.o huffman.o futils.o diter.o queue.o -lpthread
  17. +DIR=./tmp
  18. +BIN=./bin
  19. +CCFLAGS?=-O3
  20.  
  21. -arc.o: arc.c lzw.h huffman.h futils.h diter.h queue.h misc.h
  22. -   gcc -O3 -c arc.c
  23. +build-lzwarc: struct $(DIR)/arc.o $(DIR)/lzw.o $(DIR)/huffman.o $(DIR)/futils.o $(DIR)/diter.o $(DIR)/queue.o
  24. +   gcc $(CCFLAGS) -o $(BIN)/lzwarc $(DIR)/*.o -lpthread
  25.  
  26. -lzw.o: lzw.c lzw.h htbl.h bitio.h
  27. -   gcc -O3 -c lzw.c
  28. +build-lzwarc-noi: struct $(DIR)/arc.o $(DIR)/lzw.o $(DIR)/huffman.o $(DIR)/futils.o $(DIR)/diter.o $(DIR)/queue.o $(DIR)/queue.o $(DIR)/htbl.o
  29. +   gcc $(CCFLAGS) -o $(BIN)/lzwarc-noi $(DIR)/*.o -lpthread
  30.  
  31. -huffman.o: huffman.c huffman.h pqueue.h bitio.h
  32. -   gcc -O3 -c huffman.c
  33. +build-lzwarc-ncb: struct $(DIR)/arc.o $(DIR)/lzw.o $(DIR)/huffman.o $(DIR)/futils.o $(DIR)/diter.o $(DIR)/queue.o $(DIR)/queue.o $(DIR)/htbl-ncb.o
  34. +   gcc $(CCFLAGS) -o $(BIN)/lzwarc-ncb $(DIR)/*.o -lpthread
  35.  
  36. -futils.o: futils.c futils.h
  37. -   gcc -O3 -c futils.c
  38.  
  39. -diter.o: diter.c diter.h
  40. -   gcc -O3 -c diter.c
  41. +$(DIR)/arc.o: lzw.h huffman.h futils.h diter.h queue.h misc.h
  42. +$(DIR)/lzw.o: lzw.h htbl.h bitio.h
  43. +$(DIR)/huffman.o: huffman.h pqueue.h bitio.h
  44. +$(DIR)/futils.o: futils.h
  45. +$(DIR)/diter.o: diter.h
  46. +$(DIR)/queue.o: queue.h
  47. +$(DIR)/htbl.o: htbl.h
  48. +$(DIR)/htbl-ncb.o: htbl.h htbl.c
  49.  
  50. -queue.o: queue.c queue.h
  51. -   gcc -O3 -c queue.c
  52. +$(DIR)/%.o: ./%.c
  53. +   gcc $(CCFLAGS) -c $< -o $@
  54.  
  55. +clean: FORCE_
  56. +   rm -rf $(DIR)
  57. +
  58. +struct: FORCE_
  59. +   mkdir -p $(DIR)
  60. +   mkdir -p $(BIN)
  61. +
  62. +FORCE_:
  63. diff --git a/arc.c b/arc.c
  64. index 6c22267..f2f982f 100644
  65. --- a/arc.c
  66. +++ b/arc.c
  67. @@ -3,7 +3,8 @@
  68.  #include <stdint.h>
  69.  #include <string.h>
  70.  #include <pthread.h>
  71. -#include <linux/limits.h>
  72. +/* #include <linux/limits.h> */
  73. +#define PATH_MAX 4096
  74.  
  75.  #include "lzw.h"
  76.  #include "huffman.h"
  77. diff --git a/bitio.h b/bitio.h
  78. index 632b6b7..22e12c0 100644
  79. --- a/bitio.h
  80. +++ b/bitio.h
  81. @@ -15,7 +15,7 @@ typedef struct {
  82.  
  83.  #define BITIO_INIT {NULL, 0, UINTWID, 0, 0}
  84.  
  85. -inline int bget(bitio_t *this, uint64_t *pbits, int nbits)
  86. +static inline int bget(bitio_t *this, uint64_t *pbits, int nbits)
  87.  {
  88.      nbits = nbits <= UINTWID ? nbits : UINTWID;
  89.      *pbits = (this->ipos < UINTWID)
  90. @@ -38,7 +38,7 @@ inline int bget(bitio_t *this, uint64_t *pbits, int nbits)
  91.          return 0;
  92.  }
  93.  
  94. -inline void bput(bitio_t *this, uint64_t bits, int nbits)
  95. +static inline void bput(bitio_t *this, uint64_t bits, int nbits)
  96.  {
  97.      nbits = nbits <= UINTWID ? nbits : UINTWID;
  98.      if (nbits != UINTWID) bits &= (1 << nbits) - 1;
  99. @@ -52,7 +52,7 @@ inline void bput(bitio_t *this, uint64_t bits, int nbits)
  100.      this->obuf = this->opos ? bits >> (nbits - this->opos) : 0;
  101.  }
  102.  
  103. -inline void bflush(bitio_t *this)
  104. +static inline void bflush(bitio_t *this)
  105.  {
  106.      fwrite(&this->obuf, (this->opos+7)/8, 1, this->file);
  107.      this->obuf = this->opos = 0;
  108. diff --git a/diter.c b/diter.c
  109. index 3ecd958..f05fab1 100644
  110. --- a/diter.c
  111. +++ b/diter.c
  112. @@ -4,7 +4,8 @@
  113.  #include <sys/types.h>
  114.  #include <sys/stat.h>
  115.  #include <dirent.h>
  116. -#include <linux/limits.h>
  117. +/* #include <linux/limits.h> */
  118. +#define PATH_MAX 4096
  119.  
  120.  #include "diter.h"
  121.  
  122. diff --git a/htbl-ncb.c b/htbl-ncb.c
  123. new file mode 100644
  124. index 0000000..586f8de
  125. --- /dev/null
  126. +++ b/htbl-ncb.c
  127. @@ -0,0 +1,9 @@
  128. +#ifndef HTBL_NOINLINE
  129. +#error
  130. +#endif
  131. +
  132. +#include <stdint.h>
  133. +
  134. +#define HTBL_HASH(key, rng)     (*(uint32_t *)(key) % (rng))
  135. +#define HTBL_EQUAL(key1, key2)  (*(uint32_t *)(key1) == *(uint32_t *)(key2))
  136. +#include "./htbl.c"
  137. diff --git a/htbl.c b/htbl.c
  138. new file mode 100644
  139. index 0000000..9292c83
  140. --- /dev/null
  141. +++ b/htbl.c
  142. @@ -0,0 +1,78 @@
  143. +#include "./htbl.h"
  144. +
  145. +#include <stdlib.h>
  146. +#include <string.h>
  147. +
  148. +
  149. +#ifndef HTBL_HASH
  150. +#define HTBL_HASH this->hash
  151. +#endif
  152. +
  153. +#ifndef HTBL_EQUAL
  154. +#define HTBL_EQUAL this->equal
  155. +#endif
  156. +
  157. +void htbl_init(htbl_t *this, int sz,
  158. +                      int (*hash)(void *, int),
  159. +                      int (*equal)(void *, void *))
  160. +{
  161. +    this->ptr = calloc(sz, sizeof(void *));
  162. +    this->sz = sz;
  163. +    this->hash = hash;
  164. +    this->equal = equal;
  165. +}
  166. +
  167. +void htbl_free(htbl_t *this, void (*item_free)(void *))
  168. +{
  169. +    if (item_free) {
  170. +        for (int i = 0; i < this->sz; ++i) {
  171. +            if (this->ptr[i] == NULL || this->ptr[i] == &this->deleted)
  172. +                continue;
  173. +            item_free(this->ptr[i]);
  174. +        }
  175. +    }
  176. +    free(this->ptr);
  177. +}
  178. +
  179. +void **htbl_find_(htbl_t *this, void *item)
  180. +{
  181. +    void **pdel = NULL;
  182. +    int i, j;
  183. +
  184. +    for (i = HTBL_HASH(item, this->sz), j = 1;
  185. +         j < this->sz && this->ptr[i];
  186. +         i = (i+j)%this->sz, j += 2)
  187. +    {
  188. +        if (this->ptr[i] == &this->deleted)
  189. +            if (!pdel) pdel = &this->ptr[i]; else;
  190. +        else
  191. +            if (HTBL_EQUAL(this->ptr[i], item)) break;
  192. +    }
  193. +
  194. +    return j >= this->sz ? pdel
  195. +                         : this->ptr[i] || !pdel ? &this->ptr[i]
  196. +                                                 : pdel;
  197. +}
  198. +
  199. +void *htbl_find(htbl_t *this, void *item)
  200. +{
  201. +    void **pptr = htbl_find_(this, item);
  202. +    return pptr && *pptr != &this->deleted ? *pptr
  203. +                                           : NULL;
  204. +}
  205. +
  206. +int htbl_add(htbl_t *this, void *item)
  207. +{
  208. +    void **pptr = htbl_find_(this, item);
  209. +    if (!pptr)
  210. +        return -1;
  211. +    if (*pptr == NULL || *pptr == &this->deleted)
  212. +        *pptr = item;
  213. +    return 0;
  214. +}
  215. +
  216. +void htbl_del(htbl_t *this, void *item)
  217. +{
  218. +    void **pptr = htbl_find_(this, item);
  219. +    if (pptr && *pptr) *pptr = &this->deleted;
  220. +}
  221. diff --git a/htbl.h b/htbl.h
  222. index 282e5a3..6aedcfe 100644
  223. --- a/htbl.h
  224. +++ b/htbl.h
  225. @@ -1,18 +1,6 @@
  226.  #ifndef HTBL_H
  227.  #define HTBL_H
  228.  
  229. -#ifndef HTBL_HASH
  230. -#define HTBL_HASH this->hash
  231. -#endif
  232. -
  233. -#ifndef HTBL_EQUAL
  234. -#define HTBL_EQUAL this->equal
  235. -#endif
  236. -
  237. -#include <stdio.h>
  238. -#include <stdlib.h>
  239. -#include <string.h>
  240. -
  241.  typedef struct htbl {
  242.      void **ptr;
  243.      int    sz;
  244. @@ -21,7 +9,20 @@ typedef struct htbl {
  245.      int    deleted;
  246.  } htbl_t;
  247.  
  248. -inline void htbl_init(htbl_t *this, int sz,
  249. +#ifndef HTBL_NOINLINE
  250. +
  251. +#include <stdlib.h>
  252. +#include <string.h>
  253. +
  254. +#ifndef HTBL_HASH
  255. +#define HTBL_HASH this->hash
  256. +#endif
  257. +
  258. +#ifndef HTBL_EQUAL
  259. +#define HTBL_EQUAL this->equal
  260. +#endif
  261. +
  262. +static inline void htbl_init(htbl_t *this, int sz,
  263.                        int (*hash)(void *, int),
  264.                        int (*equal)(void *, void *))
  265.  {
  266. @@ -31,7 +32,7 @@ inline void htbl_init(htbl_t *this, int sz,
  267.      this->equal = equal;
  268.  }
  269.  
  270. -inline void htbl_free(htbl_t *this, void (*item_free)(void *))
  271. +static inline void htbl_free(htbl_t *this, void (*item_free)(void *))
  272.  {
  273.      if (item_free) {
  274.          for (int i = 0; i < this->sz; ++i) {
  275. @@ -43,7 +44,7 @@ inline void htbl_free(htbl_t *this, void (*item_free)(void *))
  276.      free(this->ptr);
  277.  }
  278.  
  279. -inline void **htbl_find_(htbl_t *this, void *item)
  280. +static inline void **htbl_find_(htbl_t *this, void *item)
  281.  {
  282.      void **pdel = NULL;
  283.      int i, j;
  284. @@ -63,14 +64,14 @@ inline void **htbl_find_(htbl_t *this, void *item)
  285.                                                   : pdel;
  286.  }
  287.  
  288. -inline void *htbl_find(htbl_t *this, void *item)
  289. +static inline void *htbl_find(htbl_t *this, void *item)
  290.  {
  291.      void **pptr = htbl_find_(this, item);
  292.      return pptr && *pptr != &this->deleted ? *pptr
  293.                                             : NULL;
  294.  }
  295.  
  296. -inline int htbl_add(htbl_t *this, void *item)
  297. +static inline int htbl_add(htbl_t *this, void *item)
  298.  {
  299.      void **pptr = htbl_find_(this, item);
  300.      if (!pptr)
  301. @@ -80,10 +81,23 @@ inline int htbl_add(htbl_t *this, void *item)
  302.      return 0;
  303.  }
  304.  
  305. -inline void htbl_del(htbl_t *this, void *item)
  306. +static inline void htbl_del(htbl_t *this, void *item)
  307.  {
  308.      void **pptr = htbl_find_(this, item);
  309.      if (pptr && *pptr) *pptr = &this->deleted;
  310.  }
  311.  
  312. +#else
  313. +
  314. +void htbl_init(htbl_t *this, int sz,
  315. +               int (*hash)(void *, int),
  316. +               int (*equal)(void *, void *));
  317. +void htbl_free(htbl_t *this, void (*item_free)(void *));
  318. +void **htbl_find_(htbl_t *this, void *item);
  319. +void *htbl_find(htbl_t *this, void *item);
  320. +int htbl_add(htbl_t *this, void *item);
  321. +void htbl_del(htbl_t *this, void *item);
  322. +
  323. +#endif
  324. +
  325.  #endif
  326. diff --git a/lzw.c b/lzw.c
  327. index e2bfbbb..e574e80 100644
  328. --- a/lzw.c
  329. +++ b/lzw.c
  330. @@ -5,8 +5,10 @@
  331.  #include "bitio.h"
  332.  #include "lzw.h"
  333.  
  334. +#ifndef HTBL_NOINLINE
  335.  #define HTBL_HASH(key, rng)     (*(uint32_t *)(key) % (rng))
  336.  #define HTBL_EQUAL(key1, key2)  (*(uint32_t *)(key1) == *(uint32_t *)(key2))
  337. +#endif
  338.  #include "htbl.h"
  339.  
  340.  #define DICTSIZE 0x4000
  341. @@ -18,7 +20,7 @@ typedef struct {
  342.      htbl_t htbl;
  343.  } dict_t;
  344.  
  345. -inline void dict_add(dict_t *this, int prev, int suff)
  346. +static inline void dict_add(dict_t *this, int prev, int suff)
  347.  {
  348.      if (this->nent == DICTSIZE) return;
  349.  
  350. @@ -29,7 +31,7 @@ inline void dict_add(dict_t *this, int prev, int suff)
  351.      ++this->nent;
  352.  }
  353.  
  354. -inline int dict_find(dict_t *this, int prev, int suff)
  355. +static inline int dict_find(dict_t *this, int prev, int suff)
  356.  {
  357.      int16_t ent[2];
  358.      ent[Prev] = prev;
  359. @@ -39,17 +41,37 @@ inline int dict_find(dict_t *this, int prev, int suff)
  360.      return pent ? pent - this->ent : -1;
  361.  }
  362.  
  363. -inline void dict_init(dict_t *this)
  364. +
  365. +#ifdef HTBL_NOINLINE
  366. +
  367. +int some_hash(void *key, int rng) {
  368. +
  369. +  return *(uint32_t*)key % rng;
  370. +}
  371. +
  372. +int some_equal(void *key1, void *key2) {
  373. +
  374. +  return *(uint32_t*)key1 == *(uint32_t*)key2;
  375. +}
  376. +
  377. +#else
  378. +
  379. +#define some_hash NULL
  380. +#define some_equal NULL
  381. +
  382. +#endif
  383. +
  384. +static inline void dict_init(dict_t *this)
  385.  {
  386.      this->ent = calloc(DICTSIZE, 2 * sizeof(int16_t));
  387.      this->nent = 0;
  388. -    htbl_init(&this->htbl, 33013, NULL, NULL);
  389. +    htbl_init(&this->htbl, 33013, some_hash, some_equal);
  390.  
  391.      unsigned char ch = 0;
  392.      do dict_add(this, -1, ch); while (++ch);
  393.  }
  394.  
  395. -inline void dict_free(dict_t *this)
  396. +static inline void dict_free(dict_t *this)
  397.  {
  398.      htbl_free(&this->htbl, NULL);
  399.      free(this->ent);
  400. diff --git a/misc.h b/misc.h
  401. index 87341a2..491c92f 100644
  402. --- a/misc.h
  403. +++ b/misc.h
  404. @@ -35,7 +35,7 @@ typedef char * It;
  405.  
  406.  #define ItFree(this) free(&ItInt2(this))
  407.  
  408. -inline char *pstrstr_(char **pstr, char *str_)
  409. +static inline char *pstrstr_(char **pstr, char *str_)
  410.  {
  411.      for (; *pstr; ++pstr)
  412.      {
  413. diff --git a/test.sh b/test.sh
  414. new file mode 100644
  415. index 0000000..016ee28
  416. --- /dev/null
  417. +++ b/test.sh
  418. @@ -0,0 +1,56 @@
  419. +#!/bin/sh
  420. +
  421. +abort() {
  422. +
  423. +  echo '*** an error occurred ***' >&2
  424. +  exit 1
  425. +}
  426. +
  427. +trap 'abort' 0
  428. +set -e # exit on error
  429. +
  430. +
  431. +# > /dev/null 2>$1
  432. +
  433. +run() {
  434. +
  435. +  TESTFILE="$2"
  436. +  mkdir -p ./tmp
  437. +
  438. +
  439. +  printf 'command "%s" <a/x> ./tmp/arch "%s":\n' "$1" "$2"
  440. +  
  441. +  rm -f ./tmp/arch
  442. +
  443. +  t0="$(date '+%s')"
  444. +  $1 a ./tmp/arch "$TESTFILE"
  445. +  t1="$(date '+%s')"
  446. +  printf 'compress time: %i\n' "$(expr $t1 - $t0)"
  447. +
  448. +  t0="$(stat --printf='%s' ./tmp/arch)"
  449. +  t1="$(du -s -B 1 "$TESTFILE" | cut -f 1 )"
  450. +  printf 'size: %i/100\n' $(expr "$t0" \* 100 \/ "$t1")
  451. +
  452. +
  453. +  rm -rf ./tmp/out/ && mkdir -p ./tmp/out
  454. +
  455. +  t0="$(date '+%s')"
  456. +  $1 x ./tmp/arch ./tmp/out/
  457. +  t1="$(date '+%s')"
  458. +  printf 'extract time: %i\n' "$(expr $t1 - $t0)"
  459. +  git diff --no-index "$TESTFILE" ./tmp/out/
  460. +
  461. +  return 0
  462. +}
  463. +
  464. +make clean build-lzwarc
  465. +make clean build-lzwarc-noi CCFLAGS='-O3 -DHTBL_NOINLINE'
  466. +make clean build-lzwarc-ncb CCFLAGS='-O3 -DHTBL_NOINLINE'
  467. +
  468. +run './bin/lzwarc' "$1" # прогрев
  469. +run './bin/lzwarc' "$1"
  470. +run './bin/lzwarc-noi' "$1"
  471. +run './bin/lzwarc-ncb' "$1"
  472. +
  473. +trap : 0
  474. +echo '*** success exit ***'
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top