Polarium Password Encoding

Polarium is a Nintendo DS puzzle game where you try to invert the black and white tiles, so that they match row by row, with a non-overlapping path. Polarium Advance is the Gameboy Advance sequel to Polarium. These games can save and load puzzles as a series of characters that can be written down and shared with other people.

The process that transforms the puzzles you make into passwords is simple. First the puzzle is represented as a series of 8-bit bytes, then those bytes are optionally encrypted with a 4-bit key, next they are converted to another number base (radix), and finally the converted numbers are mapped to the characters that's written down.

Keep in mind that everything is processed in little-endian order, even the individual bits in the radix conversion. This means that sometimes things will read from right to left, backwards from how we normally write.

Polarium DS codes

The information contained in Polarium [DS] are 8x8 tiles that are black or white, what portion of these tiles are used, and start/end hints coordinates. This information is packed according to Table 1.

The tile data always consists of 8x8 bits. 0 is white and 1 is black. byte 0 is the topmost row, and bit 0 is the leftmost column. All 64 tiles are packed from left to right, top to bottom. The tile data is always 8x8 bits even if the width and height is smaller. The Width and Height defines a window of the tile data that's used. Usually the bits left outside this window is changed to the default checkerboard pattern, but they can be anything.

There's some trickiness comparing hint coordinates with Width and Height. Hint coordinates include the implied border around the whole puzzle, and starts at 0. Width and Height is the portion of tiles that are included in the puzzle and starts at 1. So for a puzzle that has a width of 5 and a height of 2 the coordinates range from (0,0) to (6,3) seeing the whole board as 7 by 4.

The checksum is the sum of bytes 0 through 10 module 256.

The way that Polarium [DS] encodes the characters is that it takes 4 bytes at a time, interprets them as three 32-bit little-endian unsigned integers, converts them to decimal, 0 fills them to 10 characters, and then reverses those characters.

_ _ _ _ _ _ _ _ _ _   (mirrored bits)   bytes:
_ - - - - - - - - _   0 0 0 0 0 0 0 0   00
_ - - # # # # - - _   0 0 1 1 1 1 0 0   3C
_ - # - - - - # - _   0 1 0 0 0 0 1 0   42
_ # - # -}#{- - # _   1 0 0 1 0 1 0 1   95
_ #{-}- - - # - - _   0 0 1 0 0 0 0 1   21
_ # - - # - # - - _   0 0 1 0 1 0 0 1   29
_ - # - - - # - - _   0 0 1 0 0 0 1 0   22
_ - - # # # - - - _   0 0 0 1 1 1 0 0   1C
_ _ _ _ _ _ _ _ _ _   Start: (2,5)      52
{} = start }{ = end   End: (5,4)        45
                      Size: 8 x 8       88
                                 check: BA
 Hexadecimal:   95423C00   1C222921   BA884552
     Decimal: 2504145920 0472000801 3129492818
Final output: 0295414052 1080002740 8182949213

The Game's editor won't allow you to make entirely white or black rows, but it's a legal game mechanic and is still accepted in password form. The code is invalid if the entire visible board is white or black. The code is also invalid if the start and end hints are in the same location.

Polarium Advance codes

Polarium Advance codes are, in a lot of ways, different from Polarium [DS] codes. The codes are variable length, has some weak encryption, and can contain two different mode of tile data, for which I'll call basic and advance mode. The header comes first and is packed into the bytes according to Table 2.

The encryption key is a number from 1 to 15 indicating how bytes 2 and beyond are scrambled. Encryption key 0 is unencrypted. The checksum is the sum of unencrypted bytes 2 and beyond, module 256. The width and height are one less then the total number of tiles horizontally or vertically. They range from 3 (4x4) to 15 (16x16), which is much easier than the DS version to match up with tile coordinates. The tile coordinates range from 0 to width/height. The tile mode determines the number of bits per tile in the tile data. Tile mode 0 means 2 tile types (1 bit) per tile, and tile mode 1 means 8 tile types (3 bit) per tile. Number of steps and Difficulty hints can be anything. The Number of steps should be the minimum number of covered places required to solve the puzzle. The question mark bit can be 1 or 0, but it apparently does nothing. It's always resets to 0 when exporting the code from the game.

The number of bytes the tile data has is determined by the puzzle width, height, and tile mode. The border in included in the tile data and uses the same number of bits as the rest of the tiles. So the total number of bytes is ceiling(width * height * (mode ? 3 : 1) / 8). For example, a puzzle with a width and height of 5 tiles and advance tile mode is ceil(5 * 5 * 3 / 8) = ceil(9.375) = 10. All tiles are packed from left to right, top to bottom in little-endian order. List 3 is a list of tile codes in advance mode, basic mode is only the first two tile types with codes 0 and 1.

If the tile data is the advance tiles hurdle, white, black, multi, and space, then the bits are 111 000 001 100 110. All together and in reverse tile order that becomes 110100001000111. Then it's padded and split into 8-bit bytes, 01000111 01101000. All this because everything is done in little-endian order.

Now that all the bytes are coded they are run through some weak encryption. Each byte is separately bit rotated and xor'ed with a corresponding mask. The pairs of bit rotation and masks cycle every 8 bytes. I've prepared two tables of numbers via brute force (see Table 4). The encryption starts on the 3'rd byte (labled 2), and I also put that on the 3'rd column of the tables. So you could simply write bit_mask[key][byte_no%8] in programing languages. To encode, xor the mask then bit rotate left. To decode, bit rotate right then xor the mask.

The final step is to code the encrypted bytes into characters. This works much like packing tile values in the tile data. Each output character is 5 bits from 1 or 2 input byte. Everything is little-endian. The last character value is padded to an even 5 bits. The values then are printed according to Table 5.

  (header bytes)
   Key: 0      01
 Check:        BA
 Start: (3,2)  23
   End: (1,3)  31
  Size: (5,5)  44
 Steps: 5      04
  Diff: 0
  Mode: adv    08
            (reversed tiles)      (grouped into bytes)
 x x _ x x  111 111 110 111 111   .1111111 10111111
 x - g - x  111 110 100 110 111   ..111110 10011011 1
 _=w=g=b=_  110 011 101 010 110   ...11001 11010101 10
 x b - w x  111 000 110 001 111   ....1110 00110001 111
 x x _ x x  111 111 110 111 111   00000111 11111011 1111
                                  (5 '0' bits pad to byte)
  Data: BF FF 9B BE D5 F9 31 FE FB 07

Hexadecimal:            [  07  ][  FB  ]
[  FE  ][  31  ][  F9  ][  D5  ][  BE  ]
[  9B  ][  FF  ][  BF  ][  08  ][  04  ]
[  44  ][  31  ][  23  ][  BA  ][  01  ] <-- first byte
binary:             00000000011111111011 (4 '0' bit pad
1111111000110001111110011101010110111110       to char)
1001101111111111101111110000100000000100
0100010000110001001000111011101000000001 <-- first bit
characters:         [ 0 ][ 1 ][ + ][ $ ]
[ + ][ Y ][ Y ][ + ][ Q ][ V ][ J ][ - ]
[ Q ][ L ][ + ][ $ ][ - ][ 2 ][ 0 ][ 4 ]
[ 8 ][ M ][ Y ][ P ][ 7 ][ K ][ M ][ 1 ] <-- first char

unencrypted output:
1MK7P YM840 2-$+L Q-JVQ
+YY+$ +10

(unencrypted)                             (encrypted)
0x01                               (Using key 4) 0x41
0xBA  (mask)             (bit rotation)          0xBA
0x23 ^ 0xD5 = 0xF6   11110110 <<< 3 = 10110111   0xB7
0x31 ^ 0xA5 = 0x94   10010100 <<< 7 = 01001010   0x4A
0x44 ^ 0x04 = 0x40   01000000 <<< 1 = 10000000   0x80
0x04 ^ 0x36 = 0x32   00110010 <<< 0 = 00110010   0x32
0x08 ^ 0xC6 = 0xCE   11001110 <<< 6 = 10110011   0xB3
0xBF ^ 0x75 = 0xCA   11001010 <<< 4 = 10101100   0xAC
0xFF ^ 0x4E = 0xB1   10110001 <<< 5 = 00110110   0x36
0x9B ^ 0xD3 = 0x48   01001000 <<< 2 = 00100001   0x21
0xBE ^ 0xD5 = 0x6B   01101011 <<< 3 = 01011011   0x5B
0xD5 ^ 0xA5 = 0x70   01110000 <<< 7 = 00111000   0x38
0xF9 ^ 0x04 = 0xFD   11111101 <<< 1 = 11111011   0xFB
0x31 ^ 0x36 = 0x07   00000111 <<< 0 = 00000111   0x07
0xFE ^ 0xC6 = 0x38   00111000 <<< 6 = 00001110   0x0E
0xFB ^ 0x75 = 0x8E   10001110 <<< 4 = 11101000   0xE8
0x07 ^ 0x4E = 0x49   01001001 <<< 5 = 00101001   0x29

Hexadecimal:            [  29  ][  E8  ]
[  0E  ][  07  ][  FB  ][  38  ][  5B  ]
[  21  ][  36  ][  AC  ][  B3  ][  32  ]
[  80  ][  4A  ][  B7  ][  BA  ][  41  ]
binary:             00000010100111101000
0000111000000111111110110011100001011011
0010000100110110101011001011001100110010
1000000001001010101101111011101000000001
characters:         [ 0 ][ C ][ L ][ 8 ]
[ 1 ][ Y ][ 3 ][ + ][ W ][ K ][ 2 ][ $ ]
[ 4 ][ 4 ][ $ ][ C ][ ! ][ H ][ ! ][ P ]
[ M ][ 1 ][ 5 ][ F ][ L ][ K ][ P ][ 1 ]

Final output:
1PKLF 51MP! H!C$4 4$2KW
+3Y18 LC0

The Game's editor doesn't provide a Solid Multi-tile, but it is completely valid and works as expected. Unlike Polarium for the DS, lines of the same same color will make the whole puzzle invalid.