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.

bits -> 7 6 5 4 3 2 1 0
bytess 0-7 Tile data
byte 8 Start hint Y Start hint X
byte 9 End hint Y End hint X
byte 10 Height Width
byte 11 Checksum
Table 1: Polarium [DS] bit packing

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
Example 1: Polarium [DS] encoding

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.

bits -> 7 6 5 4 3 2 1 0
byte 0 Encryption key 0 0 0 1
byte 1 Checksum
byte 2 Start hint Y Start hint X
byte 3 End hint Y End hint X
byte 4 Height Width
byte 5 Number of steps hint
byte 6 ? 0 0 0 tile mode difficulty hint
byte 7... Tile data
Table 2: Polarium GBA bit packing

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 1 is a list of tile codes in advance mode, basic mode is only the first two tile types with codes 0 and 1.

000
White tile / Empty Border (basic mode)
001
Black tile / Hurdle Tile (basic mode)
010
Solid White tile
011
Solid Black tile
100
Multi-tile
101
Solid Multi-tile
110
Space / Empty Border (advance mode)
111
Invalid / Hurdle tile (advance mode)
List 1: Polarium Advance tile types

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 Tables 3 and 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.

Key# 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 3 4 7 2 5 6 1
2 6 2 5 1 4 0 7 3
3 4 7 6 3 5 2 1 0
4 5 2 3 7 1 0 6 4
5 6 7 0 1 3 2 4 5
6 4 1 2 3 0 7 5 6
7 5 3 7 0 2 1 6 4
8 2 0 1 6 7 3 4 5
9 4 6 5 0 2 7 1 3
A 7 4 6 2 5 1 3 0
B 6 5 4 7 1 3 0 2
C 3 7 2 0 6 1 4 5
D 0 6 4 3 1 2 5 7
E 6 1 5 7 4 0 3 2
F 4 0 3 2 6 1 7 5
Key# 0 1 2 3 4 5 6 7
0 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
1 0x09 0x6B 0xE7 0x38 0xB5 0x1C 0xBC 0x52
2 0x25 0xBC 0xB6 0x9B 0xE1 0xCA 0xA0 0x17
3 0x98 0x0A 0xED 0x9E 0x61 0x87 0xD6 0x36
4 0x4E 0xD3 0xD5 0xA5 0x04 0x36 0xC6 0x75
5 0xE5 0x01 0x15 0x26 0xBF 0xAB 0x32 0xB5
6 0xF3 0x62 0xE1 0x20 0xD9 0x6D 0xD2 0xB8
7 0xC8 0x0F 0xAC 0xA0 0x73 0x17 0xEF 0x34
8 0xBF 0xDC 0x5A 0xC5 0x15 0x27 0x65 0x10
9 0x9A 0x5C 0x9E 0xCB 0xBF 0x8A 0x03 0x05
A 0x73 0xD3 0xC9 0x81 0x7C 0x27 0x8B 0x1A
B 0xDF 0x0D 0xB3 0xAB 0x94 0xD0 0x4E 0x30
C 0x2B 0x67 0x43 0xA2 0x1A 0x3A 0xEC 0xF8
D 0xD8 0xA8 0x67 0x28 0xDA 0x0C 0xCF 0x9D
E 0x24 0xAD 0x1C 0x5E 0x4A 0x76 0x83 0xB7
F 0x94 0xF2 0xC2 0xB2 0x41 0x6F 0x6E 0xC5
Table 3 and 4: Polarium Advance encryption bit rotation and bit mask respectively.
plain = (cipher >>> rotate[key][n%8]) ^ mask[key][n%8]
cipher = (plain ^ mask[key][n%8]) <<< rotate[key][n%8]

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.

Value 0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
Character 0 1 2 3 4 5 6 7
8 9 C F H J K L
M N P Q T V W X
Y ! = $ # ? - +
Table 5: Polarium Advance character map
  (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
Example 2: Polarium Advance encoding

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.