API tools faq
paste
Guest User

Untitled

a guest
Nov 18th, 2019
231
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.85 KB | None | 0 0
raw download clone embed print report
  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 ***'
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!