Saving specfic bitsize.

Blitz3D Forums/Blitz3D Userlibs/Saving specfic bitsize.

Nexinarus

(Posted 2016) [#1]

hello i need help with saving integers in specific bit sizes. I have read all the documents from here and all over the net. But i do not know how to clean up this disaster of a code. Is there a somewhat cleaner and faster way of doing it? Keep in mind this is just an example.

mystring$="Shiftest";string to shift bits
Dim holdarray(Len(mystring$)-1);hold string as integers
;converts mystring into integers for each char and places them in an array.
For x=1 To Len(mystring$)
	holdarray(x-1)=Asc(Mid(mystring$,x,1))
	Print holdarray(x-1)
Next
Print
bit=7;0-127;for this example, no more is needed for this example

Dim storearray(Len(mystring$)-1)

spot=0
shift=0
For x=0 To Len(mystring$)-1
myinteger=myinteger+(holdarray(x)Shl shift)
shift=shift+7

If shift>7
Repeat
	storearray(spot)=myinteger Mod 256
	myinteger=(myinteger Shr 8)
	shift=shift-8
	spot=spot+1

Until shift<8
End If



Next

For x=0 To Len(mystring$)-1
Print storearray(x)
Next

;original
;1010011 83 S
;1101000 104 h
;1101001 105 i
;1100110 102 f
;1110100 116 t
;1100101 101 e
;1110011 115 s
;1110100 116 t

;saving 7-bit integers.
;1010011  NULL
;110100 0 83
;11010 01 116
;1100 110 218
;111 0100 76
;11 00101 47
;1 110011 207
; 1110100 233

Bobysait

(Posted 2016) [#2]

I don't really understand what you're looking for ( and by the way, I'm pretty sure there's nothing here related to a user library, so you're probably not on the right section, but whatever :) )

So, you're trying to compress bites into integers ?
unless you don't really need a 7 bits format, you could just use banks to store the "bites" ?
Banks allows to store unsigned bites (0-255), so it works pretty well for strings or any other value intended to be lower than 256.

Nexinarus

(Posted 2016) [#3]

ok in lzw compression when the output is more than 8-bits then it saves 9 bit integers (then 10, then 11).

I understand the lzw compression. But i never could figure out the proper way of saving the outputs except in 8bit or 16bit integers (1 or 2 bytes)

So what I was trying to do is figure out how to save integers that are only between 0-127 as data. By doing this I can then figure out the rest on my own. I was just wondering if there was a better way of doing it or at least a way to clean the code up a bit.

But thanks anyway

Dan	(Posted 2016) [#4]

the answer is simple:
for 8 bits you need only 1 byte.
for 9 to 16 bits you need 2 bytes.

As you cant save a single bit anywhere, because it will take 1 byte of place ,for example on your HD, anyway.

Floyd

(Posted 2016) [#5]

I think he is saying that 8 7-bit values can be packed into 7 8-bit bytes, saving a byte of storage.

Nexinarus

(Posted 2016) [#6]

you are right floyd

Dan	(Posted 2016) [#7]

Ok, that sounds reasonable.

i guess you should go with arrays, holding 8 elements.

then make a loop which will go through this array, and add the bits from the 8th array # to the #1-7.

Then continue with the code, adding the next bytes to 1-8 and repeating the above.

In case your string has less bytes than 8, or the end part of the string does not reach 8, you can use a variable which will detect this situation and spread the e.g 5th array to the previous 4.

Here are some bit manipulation examples: Bit Fiddling (Blitz3D / B+ version)

virtlands

(Posted 2016) [#8]

Hi Nex,
On a related topic, U can find the minimum number of required bits necessary to store a value, (v) :

The equations can be found on WolframMathWorld : http://mathworld.wolfram.com/BitLength.html

( Either variation shown here is fine, U can use Ceil, or Floor. )

Minimum BitLen = 1 +Floor(Log2(v))
Minimum BitLen = Ceil(Log2(v+1))

Minimum ByteLen = Ceil( Bitlen(v)/8.0 )

where Log2(n) is the log of n to base 2, ...

Log2(n) = Log(n)/Log(2)

-- Here is a sample Blitz3D program demonstrating BitLen --> http://tinyurl.com/gnlqkzf

virtlands

(Posted 2016) [#9]

Floyd said, "I think he is saying that 8 7-bit values can be packed into 7 8-bit bytes, saving a byte of storage."

I'm sure it can be done; It just takes a lot of complex bit shifting (and memory management).

_PJ_	(Posted 2016) [#10]

This is not so complex as it sounds.

Really you just need to reliably track:

a) How many bits to use
b) the current bit position (i.e. relative to an overarching 8, 16 or 32-bit memory space)

If a variety of different bits are going to be used, i.e.

AAA = 3 bit integer
BB = 2 bit integer
CCCCCC=6 bit integer
DDDD=4 bit integer

AAA BB CCC|CCCDDDD_|

You also need to ensure that you can reliably ensure the correct order and be aware of what sequence the bit-depth occurs.

This (which exemplified packing 3-bit integers)
http://www.blitzbasic.com/Community/posts.php?topic=106968
might be useful

But also, when a VARIABLE NUMBER OF BITS per INTEGER might be involved:


Function GetShiftedBitmapFromByte(Value,Bits,ByteStartPosition)
	;i.e. 3 bits (8th, ninth and tenth) resolve to Bit values for 1,2 and 4 By arguments : 3,8
	;If bit 8 and Bit 10 are set [128+512], the result will be as 1 and 4 i.e. 5
	
	Local ShiftedBits=Value Shr (ByteStartPosition-1)
	Local TestableValue=((1 Shl Bits) -1)
	Return ShiftedBits And TestableValue
End Function

_PJ_	(Posted 2016) [#11]

In the mentioned case of packing 8 * 7-bit values, you could store this losslessly in a minimum of 7 * 8-bit bytes

This would involve an amount of splitting the bits over certain 8-bit byte boundaries:

|AAAAAAAB|BBBBBBCC|CCCCCDDD|DDDDEEEE|EEEFFFFF|FFGGGGGG|GHHHHHHH|

There is a relational algorithm between the start of each compressed bit position and the sequence and its final position and any offset from its starting byte.
These relationships are made very clear when written out

A = 0,0,6,0
B = 7,0,5,1
C = 6,1,4,2
D = 5,2,3,3
E = 4,3,2,4
F = 3,4,1,5
G = 2,5,0,6
H = 1,6,7,6