VarINTs & Varbits

Blitz3D Forums/Blitz3D Programming/VarINTs & Varbits

virtlands (Posted 2013) [#1]

The updated version of the Varbits.BB code is shown below:

Yasha (Posted 2013) [#2]

Ha, this is some cool stuff. Nice work!

Axel Wheeler (Posted 2013) [#3]

Nice job!

virtlands (Posted 2013) [#4]

[updated]

virtlands (Posted 2013) [#5]

Here's Version 2 of my VarBits program. This is a vast improvement over the old one, and includes several new functions. The code also works with negative numbers too, but the screenshots don't yet give negative examples. It's true, 32-bit negative numbers can also be represented by Varbits. I'll be back later to explain that detail. ------ You are free to edit and use these functions as you wish, and reorganize it into your own program. ;;; This program is a study in ;;; varInts, varNibbles, and varBits ;; Updated on Feb 16, 2013 ;;; Created by VirtLands ;;; ---- THis is Version 2 ---- ; pretend that it's a series of bytes, Global Varint[6] ; Varint (base 128), 8-bit type, Least significant groups (of 7 bits) are stored first Global VarNibble[11] ; pretend that it's a series of nibbles Global VarBits[32] ; a generalization: = a series of variable-length and variable base bits. Global VarBitsShift[32] ;; record "shifts" which are powers of 2. Global VarBitsNeg ;; record the index within "VarBitsShift[..]" that is first negative or zero. Global ShiftBase = 100 ;; (To start off with, initialize ShiftBase with an "unlikely" value) VarBitsShift[0] = 1 Global MaxPos32bit = 2147483647 ;; = the max positive number for 32 bits = 2^31 -1 = $7FFFFFFF Global MaxNeg32bit = -2147483648 ;; = the max negative number for 32 bits = -2^31 = $80000000 Global decor$ = String$("_",80) Type segbytes ;;; This type is used to find out how many total bytes are in a file represented by Varbits. Field bitsLen ;; = the Varbits length, base = 2^(bitsLen-1) Field segcount ;; = the number of segments Field bytes ;; = the total number of bytes needed, (including padding bits) End Type Dim Shift(32,32) ;; = Shall become a quick shifts lookup table Global COMPACT = False ;; determines whether to output the data in a compact form, or else with spacers. ... DataSize$ = "" Graphics 1024,700,32,2 ClsColor 22,121,170 Color 10,10,10 CreateShifts() ;; Initializes the shift lookup table, ( used in the SegmentCount() Function ) ;;; THIS Function has been replaced by the better one "VarBitsSize_A(n, b)". VarBitsSize(1, 2) ;;; Initialize the VarBitsShift[...] v = VarBitsShift[1] NibbleFile$ = "VarBits.txt" fp = WriteFile(NibbleFile) Local s$, linecount .Retry Cls: Locate 1,1 Print Print" Title: A study in VarBits, VarNibbles, & Varints " Print" Created by Andy { Mr. VirtLands } , on Feb 14,2013 . Print .Start Print Print" [ A general Varbits study ] " Print" Enter the number of bits to study, Examples: 8=VarInt, 4=VarNibble, 7=Base64, etc,... " Print Color 10,10,10 Print" Valid values are between 2 and 31, Enter 0 to exit. Enter the word "+Q("COMPACT") + " to display bits without spacers " Print Color 245,245,245 s=Lower$(Input$(" > ")) : Cls : Locate 1,1 : Print compact = ( Instr(s,"compact")>0 ) ;; Shall we display it in a compact fashion ? b = Int(s) If b=0 And Len(s) Print" End of Program. " If fp Then CloseFile( fp ) End End If If (b<2 Or b>31) Or Len(s)=0 Goto Retry End If base = 1 Shl (b-1) subtitle$ = " Base = "+base+" : "+b+"-bit varBits " Print subtitle Print If fp WriteLine(fp, subtitle) WriteLine(fp,"") End If For n = 0 To 6 ;; show 6 elementary entries Print " "+ Show_bin_VarBits(n, b, 0) Next Print If fp Then WriteLine(fp,"") p=1 : linecount=0 Repeat v = Shift(b-1,p) p = p +1 ;; create some lines of information.... varbits(v, b) ;; create the varbits sequence ... If COMPACT=True line1$ = " " +PreSpace(v, 11)+" = "+VarBitsS(b) ; +" segment count = "+SegmentCount(v, b) Else line1$ = " " +Show_bin_VarBits(v, b, 0) ; +" segment count = " +SegmentCount(v, b) End If PrintLine(line1, fp) If fp WriteLine(fp,"") End If linecount = linecount +1 If linecount >=34 Print" >Touch a key to continue... " WaitKey() linecount=0 Cls : Locate 1,1 Print subtitle : Print End If Until v=0 Or v<0 If fp Then WriteLine(fp,decor) If NOFileTest Then Goto SkipFileTest Print responce$ =Lower$(Input$(" Do you wish to do a File test using Varbits? [y or n] > ")) If Not (Instr(responce,"y") Or Instr(responce,"t") Or Instr(responce,"1") ) NOFileTest = True Goto SkipFileTest End If .DoFileTest ;;; ___________ Here's your opportunity To encode a FILE into VarBits ___________ ;;; ___ Place any file names into the DATA statements at the end of this program that you wish to test. ___ If testfile$="" Then Restore List_of_Files Read testfile$ ;; If testfile = "" NOFileTest = False ; reset CloseFile fp : fp=0 datasize = "" Goto Retry End If Qtestfile$ = Q(testfile) ;; " in quotes " ft = FileType(testfile) ;; see if it exists If ft While Len(DataSize)=0 Cls : Locate 1,1 Print Print" Please enter the data sizes in bytes, that you wish to read the file "+Qtestfile+ " in . " Print" For example: " +Q(" 1 2 3 4 ") +" (1=BYTES), (2=SHORTS), (3=Tri-Bytes), (4=INTs) " Print Print" ( You may separate values with spaces ) " DataSize =Lower$(Input$(" > ")) Wend Cls :Locate 1,1 If Instr(DataSize,"1") Print Print" The following file: "+Qtestfile+ " has been read in as byte values (0-255) " File_to_Varints(testfile, 1) pauseCls() End If If Instr(DataSize,"2") Print Print" The following file: "+Qtestfile+ " has been read in as SHORT values (0-65535) " File_to_Varints(testfile, 2) pauseCls() End If If Instr(DataSize,"3") Print Print" The following file: "+Qtestfile+ " has been read in as tri-Byte values (0-16777215) " File_to_Varints(testfile, 3) pauseCls() End If If Instr(DataSize,"4") Print Print" The following file: "+Qtestfile+ " has been read in as INT values (0-4294967295) " File_to_Varints(testfile, 4) pauseCls() End If End If Goto DoFileTest .SkipFileTest Goto Start wee() ;;; weeeee! Function wee() WaitKey():End End Function ;; ____ THIS FUNCTION IS OBSOLETE and has been replaced by SegmentCount(n,b) , which is faster . ;) _____________ ;; returns the number of (variable-length) Varbits segments that are required to store ;; n in a variable-length b bit number of base 2^(b-1) ;; Function VarBitsSize(n, b) Local shift, z, x, v shift = b-1 x =1 If shiftBase <> shift For z = 1 To 40 VarBitsShift[z] = VarBitsShift[z-1] Shl shift If VarBitsShift[z] <=0 VarBitsNeg = z ;; record the negative index, and exit Exit End If Next shiftbase = shift End If If n < 0 Then Return VarBitsSize(maxpos32bit, b) v = VarBitsShift[x] While v>0 If n < v Then Return x x = x +1 v = VarBitsShift[x] Wend Return x ;; Hopefully we'll never reach "Return x" :: >>> ??? End Function ;; Returns the number of varbit "segments" required to store n in b bits, where the base = 2^(b-1) = 1 shl b Function SegmentCount(n,b) Local x,v,sh sh = b-1 ;; ... because the base=2^(b-1) If n<0 Return SegmentCount( MaxPos32bit , b) ;; all negative numbers maximize segment usage on 32 bits End If x = 1 v = shift(sh,x) ;; use a 2D lookup table While v>0 If n < v Return x End If x = x +1 v = shift(sh,x) Wend Return x ;; an error condition ??? End Function ;; 2147483647 is the highest signed positive number that can be stored in 32 bits ;; ---- This function can also be replaced by " VarBitsSize(n,4) ---- ;; Function VarNibbleSize(n) ;; returns the number of nibbles required for that varNibble If n < 0 Then Return 11 If n < 8 Then Return 1 ; 2^3 If n < 64 Then Return 2 ; 2^6 If n < 512 Then Return 3 ; 2^9 If n < 4096 Then Return 4 ; 2^12 If n < 32768 Then Return 5 ; 2^15 If n < 262144 Then Return 6 ; 2^18 If n < 2097152 Then Return 7 ; 2^21 If n < 16777216 Then Return 8 ; 2^24 If n < 134217728 Then Return 9 ; 2^27 If n < 1073741824 Then Return 10 ; 2^30 Return 11 End Function ; ; In 32-bit mode, 2147483648 is a negative number ; Function VarintSize(n) ;; returns the number of bytes required for that varint If n < 0 Then Return 6 If n < 128 Then Return 1 ; 2^7 If n < 16384 Then Return 2 ; 2^14 If n < 2097152 Then Return 3 ; 2^21 If n < 268435456 Then Return 4 ; 2^28 If n <= 2147483647 Then Return 5 ; Return 6 ; at "Return 6" the number is negative ... End Function Function VarNibble_to_N() ;; Takes a VarNibble[] array and returns it back to normal Local p=0 While( VarNibble[p] And 8 ) ;; First count the number of continuations.... p = p+1 Wend v = VarNibble[p] And 7 While p p = p -1 v = (v Shl 3) + (VarNibble[p] And 7) Wend Return v End Function Function Varint_to_N() ;; Takes a Varint[] array and returns it back to a normal (binary) value Local p=0 While( Varint[p] And 128 ) ;; First count the number of continuations.... p = p+1 Wend v = Varint[p] And 127 While p p = p -1 v = (v Shl 7) + (Varint[p] And 127) Wend Return v End Function ;; Creates a new Varbits sequence from value "n", made up of "b" bits. ;; Function VarBits(n, b) ;; creates a base (b bits) variable-var, and stores it in VarBits[] Local p=0, bits_on, high_bit, b1 high_bit = 1 Shl (b-1) bits_on = high_bit -1 b1 = b-1 Varbits[p] = n And bits_on n = n Shr b1 While(n) Varbits[p] = VarBits[p] Or high_bit p = p +1 Varbits[p] = n And bits_on n = n Shr b1 Wend End Function ;; This function takes the current Varbits sequence and turns it into a string. ;; (Each segment has b bits.) ;; Function VarBitsS$(b) Local s$, p Local high_bit = 1 Shl (b-1) s = Right$( Bin$(Varbits[p]), b ) While varbits[p] And high_bit p = p +1 s = s + Right$( Bin$(Varbits[p]), b ) Wend Return s End Function Function VarNibble(n) ;; Creates a base 8 varNibble, and stores it in VarNibble[] Local p=0 VarNibble[p] = n And 7 n = n Shr 3 While(n) VarNibble[p] = VarNibble[p] Or 8 p = p +1 VarNibble[p] = n And 7 n = n Shr 3 Wend End Function Function Varint(n) ;; Creates a base 128 varint, and stores it in Varint[] Local p=0 ; = a pointer into the Varint[] array Varint[p] = n And 127 n = n Shr 7 While(n) Varint[p] = Varint[p] Or 128 ;; set the (MSB) continuation bit p = p +1 Varint[p] = n And 127 n = n Shr 7 Wend End Function ;; option fp sends the data to a file (handle) ;; (alternate version of display_bin_VarBits(...) ;; Function Show_bin_VarBits$(n,b, fp) Local p=0, high_bit, s$, colon$ Local L colon = " : " If b=2 Then colon = ":" If b=3 Then colon = " :" VarBits(n,b) L= SegmentCount(n,b)-1 ;; start at offset 0 s = " "+prespace(n,11)+" = "+ Right$(Bin$(VarBits[0]),b) ;+colon For z=1 To L s = s +colon +Right$(Bin$(VarBits[z]),b) ;+colon Next If fp WriteLine(fp,s) End If Return s End Function Function display_bin_VarBits(n,b, fp) Local p=0, high_bit, s$, colon$ colon = " : " If b=2 Then colon = ":" If b=3 Then colon = " :" high_bit = 1 Shl b VarBits(n,b) Write " "+n+" = "+Mid$( Bin$(VarBits[p]), 33-b,b) While( VarBits[p] And high_bit ) p = p +1 Write colon+Mid$( Bin$(VarBits[p]), 33-b,b) Wend If fp p=0 s = " "+ Str$(n)+" = "+Mid$( Bin$(VarBits[p]), 33-b,b) While( VarBits[p] And high_bit ) p = p +1 s = s +colon+Mid$( Bin$(VarBits[p]), 33-b,b) Wend WriteLine(fp,s) End If End Function Function display_bin_VarNibble(n) Local p=0 VarNibble(n) Write " "+n+" = "+Mid$( Bin$(VarNibble[p]), 29,4) +" : " While( VarNibble[p] And 8 ) p = p +1 Write Mid$( Bin$(VarNibble[p]), 29,4) +" : " Wend End Function Function display_bin_Varint(n) ; displays a number as a varint, in binary form, least significant groups first Varint(n) Local p = 0 Write " "+n+" = "+Mid$( Bin$(Varint[p]), 25,8) +" : " While( Varint[p] And 128 ) p = p +1 Write Mid$( Bin$(Varint[p]), 25,8) +" : " Wend End Function ;; A simple function that returns the max value that ;; can be stored in 1 segment ONLY of a varbits sequence of length b bits (= base 2^b) ;; Function VarBitsMAXValue(b) Return (1 Shl (b-1)) -1 End Function ;; Takes a Varbits sequence where each segment length =b bits, and returns it back to a normal number Function VarBits_to_N(b) ;; Local p=0, bits_on, high_bit, b1 high_bit = (1 Shl (b-1)) bits_on = high_bit -1 b1 = b-1 While( VarBits[p] And high_bit ) ;; First count the number of continuations.... p = p+1 Wend v = VarBits[p] And bits_on While p p = p -1 v = (v Shl b1) + (VarBits[p] And bits_on) Wend Return v End Function ;; This next function evaluates a file using varBits of various bases (2 to 31) ;; and helps you determine which base is best for storage purposes ( least bytes = better ) ;; ;; The statistical data shall be displayed ;; ;; data_size = the amount of bytes to read at a time, usually it is 1,2,4, (that is "BYTE", "SHORT", "INT") ;; Function File_to_Varints(file$, data_size) Local FSize, chunks, fp, remain, z, v Local segmentcount[31] ;; This array shall store segment counts that resul (when storing in Varbits) Local s$, info$[31] fp = ReadFile(file) If fp=0 Then Return 0 Fsize = FileSize(file) chunks = Fsize/data_size remaining = Fsize Mod data_size Select Data_size Case 1 ;; read in 1 byte at a time For z=1 To chunks v = ReadByte(fp) For b=2 To 31 ;; -- this is the bits length, (not to be confused with base) segmentcount[b] = segmentcount[b] + segmentCount(v, b) Next Next Case 2 ;; read in a 2 bytes at a time, ( also known as unsigned SHORTs ) For z=1 To chunks v = ReadByte(fp) Or (ReadByte(fp) Shl 8) ;; better to do this to make the value always positive For b=2 To 31 segmentcount[b] = segmentcount[b] + segmentcount(v,b) Next Next If remaining ;; ... if there were an ODD number of bytes, .... v = ReadByte(fp) For b=2 To 31 segmentcount[b] = segmentcount[b] + segmentcount(v,b) Next End If Case 3 For z=1 To chunks ;; read in a 3-byte value v = ReadByte(fp) Or (ReadByte(fp) Shl 8) Or (ReadByte(fp) Shl 16) For b=2 To 31 segmentcount[b] = segmentcount[b] + segmentcount(v,b) Next Next If remaining v = ReadByte(fp) Or (ReadByte(fp) Shl 8) ;; ( A "ReadByte" past EOF results in a zero. ) For b=2 To 31 segmentcount[b] = segmentcount[b] + segmentcount(v,b) Next End If Case 4 For z=1 To chunks ;; read in a 4-byte value, also known as an INT v = ReadInt(fp) Or (ReadByte(fp) Shl 8) Or (ReadByte(fp) Shl 16) For b=2 To 31 segmentcount[b] = segmentcount[b] + segmentcount(v,b) Next Next If remaining v = ReadByte(fp) Or (ReadByte(fp) Shl 8) Or (ReadByte(fp) Shl 16) For b=2 To 31 segmentcount[b] = segmentcount[b] + segmentcount(v,b) Next End If End Select CloseFile(fp) Print Print" The results are sorted by total BYTES per file." Print" The entries with lower bytes used are obviously better than the ones with higher . " Print For b =2 To 31 bytes = Ceil( segmentcount[b]*b/8.0 ) s = " bytes used=" +PreSpace(bytes, 7)+" : bits len= " +PreSpace(b, 2)+" : base= " +PreSpace(1 Shl (b-1), 11) s = s + " : segment count = " +PreSpace(segmentcount[b],5) info[b] = s Next info[1] = " bytes used=" +PreSpace(FSize, 7)+" : <<---- THis is the original file size, WITHOUT Varints " ;; use a simple bubble sort to sort the data by " bytes USED " : unsorted=1 While unsorted unsorted=0 For b = 2 To 31 If info[b]<info[b-1] unsorted = True s = info[b] info[b] = info[b-1] info[b-1] = s End If Next Wend For b =1 To 31 Print info[b] Next Print : Print End Function ;; This creates a faster shift lookup routine, but it uses more memory ;; (Initializes a 2D array) Function CreateShifts() Local s,z For z = 1 To 32 Shift(z,0) = 1 ;; set all index "0"s to "1" Next For s = 0 To 32 For z = 1 To 32 Shift(s, z) = shift(s, z-1) Shl s Next Next End Function ;; This function writes a line to the screen, ;; and optionally writes the same string to a file ;; Function printLine(s$, fp) Print s$ If fp WriteLine(fp, s) End If End Function ; This formats data by prefixing it with spaces, so that the total string size = formatSize Function PreSpace$(n, formatSize) Local s$ s = n s = String$(" ", formatSize - Len(s)) +s Return s End Function ; This function is just like the previous, except that its input variable is a string. Function PreSpaceS$(s$, formatSize) ;s = String$(" ", formatSize - Len(s)) +s ;Return s Return String$(" ", formatSize - Len(s)) +s End Function ;; Encase a string in quotes Function Q$(s$) Local chr34$ = Chr$(34) Return Chr34 + s + Chr34 End Function Function PauseCLS() Print" Touch a key to continue " : WaitKey() Cls:Locate 1,1 End Function ;; Place here any files that you wish to perform a Varints test on :::::: ;; For program detection, the last entry must be "" to indicate " end_of_list " ;;; .List_of_Files ;;;; replace these with your own files ;;;; Data "Varbits__.txt" Data "sequence_of_all_chrs(0-255).txt" Data "1000Xchr127.txt" Data "1000xchr32.txt" Data "" I tested it for hours and hours... If you discover any bugs, let me know. I'll be back later on to explain Varbits in more detail later; I'm out of time for today. ;)

virtlands (Posted 2013) [#6]

I had some time to make this diagram to help explain this stuff. The function VarBits(n, b) will generative results for both positive and negative numbers (n<0 OR n>0), ( b=bits length, and n=the number to convert ) [ This screenshot shows a few negative values: ] This next screenshot demonstrates a few positive values, where bits_length = 3 and base=4 : Most of the time, varbits (VarNibbles, VarInts, etc) won't be used for much, since obviously the compression result isn't that great, so this is just a study in concept.