Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- diff --git a/.gitignore b/.gitignore
- new file mode 100644
- index 0000000..6fc4f0c
- --- /dev/null
- +++ b/.gitignore
- @@ -0,0 +1,2 @@
- +tmp/
- +bin/
- \ No newline at end of file
- diff --git a/Makefile b/Makefile
- index 72310a6..aec0462 100644
- --- a/Makefile
- +++ b/Makefile
- @@ -1,21 +1,34 @@
- -lzwarc: arc.o lzw.o huffman.o futils.o diter.o queue.o
- - gcc -o lzwarc arc.o lzw.o huffman.o futils.o diter.o queue.o -lpthread
- +DIR=./tmp
- +BIN=./bin
- +CCFLAGS?=-O3
- -arc.o: arc.c lzw.h huffman.h futils.h diter.h queue.h misc.h
- - gcc -O3 -c arc.c
- +build-lzwarc: struct $(DIR)/arc.o $(DIR)/lzw.o $(DIR)/huffman.o $(DIR)/futils.o $(DIR)/diter.o $(DIR)/queue.o
- + gcc $(CCFLAGS) -o $(BIN)/lzwarc $(DIR)/*.o -lpthread
- -lzw.o: lzw.c lzw.h htbl.h bitio.h
- - gcc -O3 -c lzw.c
- +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
- + gcc $(CCFLAGS) -o $(BIN)/lzwarc-noi $(DIR)/*.o -lpthread
- -huffman.o: huffman.c huffman.h pqueue.h bitio.h
- - gcc -O3 -c huffman.c
- +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
- + gcc $(CCFLAGS) -o $(BIN)/lzwarc-ncb $(DIR)/*.o -lpthread
- -futils.o: futils.c futils.h
- - gcc -O3 -c futils.c
- -diter.o: diter.c diter.h
- - gcc -O3 -c diter.c
- +$(DIR)/arc.o: lzw.h huffman.h futils.h diter.h queue.h misc.h
- +$(DIR)/lzw.o: lzw.h htbl.h bitio.h
- +$(DIR)/huffman.o: huffman.h pqueue.h bitio.h
- +$(DIR)/futils.o: futils.h
- +$(DIR)/diter.o: diter.h
- +$(DIR)/queue.o: queue.h
- +$(DIR)/htbl.o: htbl.h
- +$(DIR)/htbl-ncb.o: htbl.h htbl.c
- -queue.o: queue.c queue.h
- - gcc -O3 -c queue.c
- +$(DIR)/%.o: ./%.c
- + gcc $(CCFLAGS) -c $< -o $@
- +clean: FORCE_
- + rm -rf $(DIR)
- +
- +struct: FORCE_
- + mkdir -p $(DIR)
- + mkdir -p $(BIN)
- +
- +FORCE_:
- diff --git a/arc.c b/arc.c
- index 6c22267..f2f982f 100644
- --- a/arc.c
- +++ b/arc.c
- @@ -3,7 +3,8 @@
- #include <stdint.h>
- #include <string.h>
- #include <pthread.h>
- -#include <linux/limits.h>
- +/* #include <linux/limits.h> */
- +#define PATH_MAX 4096
- #include "lzw.h"
- #include "huffman.h"
- diff --git a/bitio.h b/bitio.h
- index 632b6b7..22e12c0 100644
- --- a/bitio.h
- +++ b/bitio.h
- @@ -15,7 +15,7 @@ typedef struct {
- #define BITIO_INIT {NULL, 0, UINTWID, 0, 0}
- -inline int bget(bitio_t *this, uint64_t *pbits, int nbits)
- +static inline int bget(bitio_t *this, uint64_t *pbits, int nbits)
- {
- nbits = nbits <= UINTWID ? nbits : UINTWID;
- *pbits = (this->ipos < UINTWID)
- @@ -38,7 +38,7 @@ inline int bget(bitio_t *this, uint64_t *pbits, int nbits)
- return 0;
- }
- -inline void bput(bitio_t *this, uint64_t bits, int nbits)
- +static inline void bput(bitio_t *this, uint64_t bits, int nbits)
- {
- nbits = nbits <= UINTWID ? nbits : UINTWID;
- if (nbits != UINTWID) bits &= (1 << nbits) - 1;
- @@ -52,7 +52,7 @@ inline void bput(bitio_t *this, uint64_t bits, int nbits)
- this->obuf = this->opos ? bits >> (nbits - this->opos) : 0;
- }
- -inline void bflush(bitio_t *this)
- +static inline void bflush(bitio_t *this)
- {
- fwrite(&this->obuf, (this->opos+7)/8, 1, this->file);
- this->obuf = this->opos = 0;
- diff --git a/diter.c b/diter.c
- index 3ecd958..f05fab1 100644
- --- a/diter.c
- +++ b/diter.c
- @@ -4,7 +4,8 @@
- #include <sys/types.h>
- #include <sys/stat.h>
- #include <dirent.h>
- -#include <linux/limits.h>
- +/* #include <linux/limits.h> */
- +#define PATH_MAX 4096
- #include "diter.h"
- diff --git a/htbl-ncb.c b/htbl-ncb.c
- new file mode 100644
- index 0000000..586f8de
- --- /dev/null
- +++ b/htbl-ncb.c
- @@ -0,0 +1,9 @@
- +#ifndef HTBL_NOINLINE
- +#error
- +#endif
- +
- +#include <stdint.h>
- +
- +#define HTBL_HASH(key, rng) (*(uint32_t *)(key) % (rng))
- +#define HTBL_EQUAL(key1, key2) (*(uint32_t *)(key1) == *(uint32_t *)(key2))
- +#include "./htbl.c"
- diff --git a/htbl.c b/htbl.c
- new file mode 100644
- index 0000000..9292c83
- --- /dev/null
- +++ b/htbl.c
- @@ -0,0 +1,78 @@
- +#include "./htbl.h"
- +
- +#include <stdlib.h>
- +#include <string.h>
- +
- +
- +#ifndef HTBL_HASH
- +#define HTBL_HASH this->hash
- +#endif
- +
- +#ifndef HTBL_EQUAL
- +#define HTBL_EQUAL this->equal
- +#endif
- +
- +void htbl_init(htbl_t *this, int sz,
- + int (*hash)(void *, int),
- + int (*equal)(void *, void *))
- +{
- + this->ptr = calloc(sz, sizeof(void *));
- + this->sz = sz;
- + this->hash = hash;
- + this->equal = equal;
- +}
- +
- +void htbl_free(htbl_t *this, void (*item_free)(void *))
- +{
- + if (item_free) {
- + for (int i = 0; i < this->sz; ++i) {
- + if (this->ptr[i] == NULL || this->ptr[i] == &this->deleted)
- + continue;
- + item_free(this->ptr[i]);
- + }
- + }
- + free(this->ptr);
- +}
- +
- +void **htbl_find_(htbl_t *this, void *item)
- +{
- + void **pdel = NULL;
- + int i, j;
- +
- + for (i = HTBL_HASH(item, this->sz), j = 1;
- + j < this->sz && this->ptr[i];
- + i = (i+j)%this->sz, j += 2)
- + {
- + if (this->ptr[i] == &this->deleted)
- + if (!pdel) pdel = &this->ptr[i]; else;
- + else
- + if (HTBL_EQUAL(this->ptr[i], item)) break;
- + }
- +
- + return j >= this->sz ? pdel
- + : this->ptr[i] || !pdel ? &this->ptr[i]
- + : pdel;
- +}
- +
- +void *htbl_find(htbl_t *this, void *item)
- +{
- + void **pptr = htbl_find_(this, item);
- + return pptr && *pptr != &this->deleted ? *pptr
- + : NULL;
- +}
- +
- +int htbl_add(htbl_t *this, void *item)
- +{
- + void **pptr = htbl_find_(this, item);
- + if (!pptr)
- + return -1;
- + if (*pptr == NULL || *pptr == &this->deleted)
- + *pptr = item;
- + return 0;
- +}
- +
- +void htbl_del(htbl_t *this, void *item)
- +{
- + void **pptr = htbl_find_(this, item);
- + if (pptr && *pptr) *pptr = &this->deleted;
- +}
- diff --git a/htbl.h b/htbl.h
- index 282e5a3..6aedcfe 100644
- --- a/htbl.h
- +++ b/htbl.h
- @@ -1,18 +1,6 @@
- #ifndef HTBL_H
- #define HTBL_H
- -#ifndef HTBL_HASH
- -#define HTBL_HASH this->hash
- -#endif
- -
- -#ifndef HTBL_EQUAL
- -#define HTBL_EQUAL this->equal
- -#endif
- -
- -#include <stdio.h>
- -#include <stdlib.h>
- -#include <string.h>
- -
- typedef struct htbl {
- void **ptr;
- int sz;
- @@ -21,7 +9,20 @@ typedef struct htbl {
- int deleted;
- } htbl_t;
- -inline void htbl_init(htbl_t *this, int sz,
- +#ifndef HTBL_NOINLINE
- +
- +#include <stdlib.h>
- +#include <string.h>
- +
- +#ifndef HTBL_HASH
- +#define HTBL_HASH this->hash
- +#endif
- +
- +#ifndef HTBL_EQUAL
- +#define HTBL_EQUAL this->equal
- +#endif
- +
- +static inline void htbl_init(htbl_t *this, int sz,
- int (*hash)(void *, int),
- int (*equal)(void *, void *))
- {
- @@ -31,7 +32,7 @@ inline void htbl_init(htbl_t *this, int sz,
- this->equal = equal;
- }
- -inline void htbl_free(htbl_t *this, void (*item_free)(void *))
- +static inline void htbl_free(htbl_t *this, void (*item_free)(void *))
- {
- if (item_free) {
- for (int i = 0; i < this->sz; ++i) {
- @@ -43,7 +44,7 @@ inline void htbl_free(htbl_t *this, void (*item_free)(void *))
- free(this->ptr);
- }
- -inline void **htbl_find_(htbl_t *this, void *item)
- +static inline void **htbl_find_(htbl_t *this, void *item)
- {
- void **pdel = NULL;
- int i, j;
- @@ -63,14 +64,14 @@ inline void **htbl_find_(htbl_t *this, void *item)
- : pdel;
- }
- -inline void *htbl_find(htbl_t *this, void *item)
- +static inline void *htbl_find(htbl_t *this, void *item)
- {
- void **pptr = htbl_find_(this, item);
- return pptr && *pptr != &this->deleted ? *pptr
- : NULL;
- }
- -inline int htbl_add(htbl_t *this, void *item)
- +static inline int htbl_add(htbl_t *this, void *item)
- {
- void **pptr = htbl_find_(this, item);
- if (!pptr)
- @@ -80,10 +81,23 @@ inline int htbl_add(htbl_t *this, void *item)
- return 0;
- }
- -inline void htbl_del(htbl_t *this, void *item)
- +static inline void htbl_del(htbl_t *this, void *item)
- {
- void **pptr = htbl_find_(this, item);
- if (pptr && *pptr) *pptr = &this->deleted;
- }
- +#else
- +
- +void htbl_init(htbl_t *this, int sz,
- + int (*hash)(void *, int),
- + int (*equal)(void *, void *));
- +void htbl_free(htbl_t *this, void (*item_free)(void *));
- +void **htbl_find_(htbl_t *this, void *item);
- +void *htbl_find(htbl_t *this, void *item);
- +int htbl_add(htbl_t *this, void *item);
- +void htbl_del(htbl_t *this, void *item);
- +
- +#endif
- +
- #endif
- diff --git a/lzw.c b/lzw.c
- index e2bfbbb..e574e80 100644
- --- a/lzw.c
- +++ b/lzw.c
- @@ -5,8 +5,10 @@
- #include "bitio.h"
- #include "lzw.h"
- +#ifndef HTBL_NOINLINE
- #define HTBL_HASH(key, rng) (*(uint32_t *)(key) % (rng))
- #define HTBL_EQUAL(key1, key2) (*(uint32_t *)(key1) == *(uint32_t *)(key2))
- +#endif
- #include "htbl.h"
- #define DICTSIZE 0x4000
- @@ -18,7 +20,7 @@ typedef struct {
- htbl_t htbl;
- } dict_t;
- -inline void dict_add(dict_t *this, int prev, int suff)
- +static inline void dict_add(dict_t *this, int prev, int suff)
- {
- if (this->nent == DICTSIZE) return;
- @@ -29,7 +31,7 @@ inline void dict_add(dict_t *this, int prev, int suff)
- ++this->nent;
- }
- -inline int dict_find(dict_t *this, int prev, int suff)
- +static inline int dict_find(dict_t *this, int prev, int suff)
- {
- int16_t ent[2];
- ent[Prev] = prev;
- @@ -39,17 +41,37 @@ inline int dict_find(dict_t *this, int prev, int suff)
- return pent ? pent - this->ent : -1;
- }
- -inline void dict_init(dict_t *this)
- +
- +#ifdef HTBL_NOINLINE
- +
- +int some_hash(void *key, int rng) {
- +
- + return *(uint32_t*)key % rng;
- +}
- +
- +int some_equal(void *key1, void *key2) {
- +
- + return *(uint32_t*)key1 == *(uint32_t*)key2;
- +}
- +
- +#else
- +
- +#define some_hash NULL
- +#define some_equal NULL
- +
- +#endif
- +
- +static inline void dict_init(dict_t *this)
- {
- this->ent = calloc(DICTSIZE, 2 * sizeof(int16_t));
- this->nent = 0;
- - htbl_init(&this->htbl, 33013, NULL, NULL);
- + htbl_init(&this->htbl, 33013, some_hash, some_equal);
- unsigned char ch = 0;
- do dict_add(this, -1, ch); while (++ch);
- }
- -inline void dict_free(dict_t *this)
- +static inline void dict_free(dict_t *this)
- {
- htbl_free(&this->htbl, NULL);
- free(this->ent);
- diff --git a/misc.h b/misc.h
- index 87341a2..491c92f 100644
- --- a/misc.h
- +++ b/misc.h
- @@ -35,7 +35,7 @@ typedef char * It;
- #define ItFree(this) free(&ItInt2(this))
- -inline char *pstrstr_(char **pstr, char *str_)
- +static inline char *pstrstr_(char **pstr, char *str_)
- {
- for (; *pstr; ++pstr)
- {
- diff --git a/test.sh b/test.sh
- new file mode 100644
- index 0000000..016ee28
- --- /dev/null
- +++ b/test.sh
- @@ -0,0 +1,56 @@
- +#!/bin/sh
- +
- +abort() {
- +
- + echo '*** an error occurred ***' >&2
- + exit 1
- +}
- +
- +trap 'abort' 0
- +set -e # exit on error
- +
- +
- +# > /dev/null 2>$1
- +
- +run() {
- +
- + TESTFILE="$2"
- + mkdir -p ./tmp
- +
- +
- + printf 'command "%s" <a/x> ./tmp/arch "%s":\n' "$1" "$2"
- +
- + rm -f ./tmp/arch
- +
- + t0="$(date '+%s')"
- + $1 a ./tmp/arch "$TESTFILE"
- + t1="$(date '+%s')"
- + printf 'compress time: %i\n' "$(expr $t1 - $t0)"
- +
- + t0="$(stat --printf='%s' ./tmp/arch)"
- + t1="$(du -s -B 1 "$TESTFILE" | cut -f 1 )"
- + printf 'size: %i/100\n' $(expr "$t0" \* 100 \/ "$t1")
- +
- +
- + rm -rf ./tmp/out/ && mkdir -p ./tmp/out
- +
- + t0="$(date '+%s')"
- + $1 x ./tmp/arch ./tmp/out/
- + t1="$(date '+%s')"
- + printf 'extract time: %i\n' "$(expr $t1 - $t0)"
- + git diff --no-index "$TESTFILE" ./tmp/out/
- +
- + return 0
- +}
- +
- +make clean build-lzwarc
- +make clean build-lzwarc-noi CCFLAGS='-O3 -DHTBL_NOINLINE'
- +make clean build-lzwarc-ncb CCFLAGS='-O3 -DHTBL_NOINLINE'
- +
- +run './bin/lzwarc' "$1" # прогрев
- +run './bin/lzwarc' "$1"
- +run './bin/lzwarc-noi' "$1"
- +run './bin/lzwarc-ncb' "$1"
- +
- +trap : 0
- +echo '*** success exit ***'
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement