Base-96 Encoding

[walker7]

One form of data encoding that seems interesting is base-96. With base-96, you could effectively translate a set of data into ASCII characters. Base-96 uses digits 0-95.

For example, the space character (ASCII $20) would represent 0, "!" represents 1, etc.

The string "1234" in ASCII-hex is:
$31 $32 $33 $34

But these bytes range from $20-$7F (32-127 in decimal). To get their actual values, all you have to do is subtract $20 from each byte. Using the above as an example, you get:
$11 $12 $13 $14
That represents the digits 17, 18, 19, and 20 in base-96. Now, if you were to interpret these in little-endian order (least significant digit first), you would get this result:
17 * 96^0 + 18 * 96^1 + 19 * 96^2 + 20 * 96^3 = 17,871,569


One of the most intriguing things about base-96 is encryption. There can be many different ways of doing so. One obvious way is to just simply add an offset (ranging from 0-95), then subtracting 96 if the result is 96 or greater. Assume that the byte value ranges from 0-95, not 32-127. In C++, this is represented by:

Code: Select all

c[n] = (c[n] + k) % 96; // c[n] = digit in base-96, k = offset (0-95)

And in 68K assembly, it would be:

Code: Select all

move.b  (a0),d0
addi.b  #k,d0
cmpi.b  #96,d0
bcs.b   .1
subi.b  #96,d0
.1:
move.b  d0,(a0)

Another way to encrypt would be to use XOR, but you can only encrypt the last 5 bits and not go outside the range of 0-95. In C++:

Code: Select all

c[n] = c[n] ^ k; // c[n] = digit in base-96, k = offset (0-31)

And in 68K:

Code: Select all

move.b  (a0),d0
eori.b  #k,d0
move.b  d0,(a0)

What are some more clever or interesting ways that you could encrypt base-96 strings?

[haroldoop]

Well, you could just do whatever binary encryption you want to do on the original binary data, and the convert the resulting encrypted data to base 96; you'll get better and more flexible encryption in that way.
But, anyway, what's your intended use for base 96?

[walker7]

Well, you could just do whatever binary encryption you want to do on the original binary data, and the convert the resulting encrypted data to base 96; you'll get better and more flexible encryption in that way.
But, anyway, what's your intended use for base 96?

Base-96 allows you to use the full ASCII character set to compactly represent a set of data. Passwords that store a whole lot of data could use this encoding. You could also use it to effectively create save-states in a game.

This is the procedure for storing a bit into a Base-96 number. Assume that digits range from 0-95:

• 1. Set the carry to the input bit.
• 2. Double the digit, and add the carry. The digit can now range from 0-191.
• 3. If the digit became 96 or greater, set the carry, and subtract 96 from the digit. Otherwise, clear the carry, and don't subtract 96 from the digit.
• 4. Repeat from Step 2 for the next digit.
• 5. If the carry out of the most significant digit (from Step 3) was a 1, add a new digit to the string, with a value of 1.

This is the procedure for reading a bit from a Base-96 number. Again, assume that digits range from 0-95:

• 1. Shift the most significant digit right one bit into the carry.
• 2. For the next digit, if the carry was set, add 96 to that digit. Then, regardless of whether you added 96 or not, shift the digit right one bit into the carry.
• 3. Repeat Step 2 for the remaining digits.
• 4. The output bit is the carry out of the least significant digit.

[haroldoop]

I can see how this could work for passwords, but not so much for savestates... in that last case, it could actually reduce storage effectiveness for binary data, since save RAM can work with full-blown base 256 with no problems; it could produce some small improvement for text storage, but savegames generally don't have to store much text.

[walker7]

I can see how this could work for passwords, but not so much for savestates... in that last case, it could actually reduce storage effectiveness for binary data, since save RAM can work with full-blown base 256 with no problems; it could produce some small improvement for text storage, but savegames generally don't have to store much text.

When I said about making save-states, this is what I mean:

In The Legend of Zelda and Zelda II: The Adventures of Link for the NES, you were allowed to store up to 3 games. In the file-select screen, each character had a name, and it showed their life hearts (in Zelda 1), or their power levels (in Zelda 2). These also stored items and other pieces of information.

On Sonic 3 for the Sega Genesis, there were 6 save slots (in S3&K, there were 8).

In these cases, all the information required for these saved games could be represented compactly in base-96.

[Chilly Willy]

It's not worth the effort. Flash carts allow 32KB of sram or more, and so do emulators. Trying to scrounge for bytes was only needed in the old days when you had 256 or 512 bytes of sram. What you suggest might save a few bytes, but in 32KB, who cares? No one here, that's for certain.

If you had 32K of data to store and wanted to save space, you'd use regular compression like lz77 or lzss, not a compact representation. So it's doubly useless for folks doing homebrew here. It's interesting from a technical point of view, but I'd never use it in an actual program.

[kubilus1]

base-96 (or base 64 or anything else like this) would increase, not decrease the size to store the same amount of binary data. The purpose of ascii type encoding such as base-96 is so that the resulting data is printable.

I am in the email business and such encoding is a way to send binary data directly within the body of an email, for instance.

Also, encoding != encryption. Base 96 encoding would be as ineffective as rot13 for hiding passwords. Anyone could simply decode the data. You would want to look at a one way hash with a salt for password matching.