From dd47f287898ea0f976dc1d737eda47d8690e621c Mon Sep 17 00:00:00 2001 From: Tomas Valla Date: Thu, 28 Mar 2013 14:12:23 +0100 Subject: [PATCH] Varints: Added documentation. --- ucw/doc/Makefile | 2 +- ucw/doc/index.txt | 1 + ucw/doc/varint.txt | 4 ++++ ucw/varint.h | 14 +++++++------- 4 files changed, 13 insertions(+), 8 deletions(-) create mode 100644 ucw/doc/varint.txt diff --git a/ucw/doc/Makefile b/ucw/doc/Makefile index 4da7cf8c..7a018f3d 100644 --- a/ucw/doc/Makefile +++ b/ucw/doc/Makefile @@ -2,7 +2,7 @@ DIRS+=ucw/doc -UCW_DOCS=basics log fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap compress sort hashtable relnotes trans string time daemon signal +UCW_DOCS=basics log fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap compress sort hashtable relnotes trans string time daemon signal varint UCW_INDEX=$(o)/ucw/doc/def_index.html UCW_DOCS_HTML=$(addprefix $(o)/ucw/doc/,$(addsuffix .html,$(UCW_DOCS))) diff --git a/ucw/doc/index.txt b/ucw/doc/index.txt index e449c755..f8240068 100644 --- a/ucw/doc/index.txt +++ b/ucw/doc/index.txt @@ -33,6 +33,7 @@ Modules - <> - <> - <> +- <> - <> - <> - <> diff --git a/ucw/doc/varint.txt b/ucw/doc/varint.txt new file mode 100644 index 00000000..85687bf1 --- /dev/null +++ b/ucw/doc/varint.txt @@ -0,0 +1,4 @@ +Efficient encoding of u64 to byte sequence +========================================== + +!!ucw/varint.h diff --git a/ucw/varint.h b/ucw/varint.h index 79952dc1..2688a088 100644 --- a/ucw/varint.h +++ b/ucw/varint.h @@ -13,15 +13,15 @@ /*** * The encoding works in the following way: * - * First byte Stored values + * First byte Stored values * - * 0xxxxxxx 7 bits - * 10xxxxxx +1 byte 14 bits, value shifted by 2^7 - * 110xxxxx +2 bytes 21 bits, value shifted by 2^7+2^14 - * 1110xxxx +3 bytes 28 bits, value shifted by 2^7+2^14+2^21 + * 0xxxxxxx 7 bits + * 10xxxxxx +1 byte 14 bits, value shifted by 2^7 + * 110xxxxx +2 bytes 21 bits, value shifted by 2^7+2^14 + * 1110xxxx +3 bytes 28 bits, value shifted by 2^7+2^14+2^21 * .... - * 11111110 +7 bytes 56 bits, value shifted by 2^7+2^14+2^21+2^28+2^35+2^42 - * 11111111 +8 bytes full 64 bits, value shifted by 2^7+2^14+2^21+2^28+2^35+2^42+2^56 + * 11111110 +7 bytes 56 bits, value shifted by 2^7+2^14+2^21+2^28+2^35+2^42 + * 11111111 +8 bytes full 64 bits, value shifted by 2^7+2^14+2^21+2^28+2^35+2^42+2^56 * * The values are stored in bigendian to allow lexicographic sorting. * The encoding and algorithms are aimed to be optimised for storing shorter numbers. -- 2.39.2