Polarium Password Encoding

[puzzle codes for polarium and polarium advance]

This blog post is a long overdue update to the info I found years ago.

Intro

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 numbers called octets, then those octets 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 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 ->76543210
octets 0-7Tile data
octet 8Start hint YStart hint X
octet 9End hint YEnd hint X
octet 10HeightWidth
octet 11Checksum
Table 1: Polarium [DS] bit packing

The tile data always consists of 8x8 bits. 0 is white and 1 is black. octet 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 octets 0 through 10 module 256.

The way that Polarium [DS] codes octets to characters is that is takes 4 octets 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)   octets:
_ - - - - - - - - _   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 octets according to Table 2.

bits ->76543210
octet 0Encryption key0001
octet 1Checksum
octet 2Start hint YStart hint X
octet 3End hint YEnd hint X
octet 4HeightWidth
octet 5Number of steps hint
octet 6?000tile modedifficulty hint
octet 7...Tile data
Table 2: Polarium GBA bit packing

The encryption key is a number from 1 to 15 indicating how octets 2 and beyond are scrambled, 0 is unencrypted. The checksum is the sum of unencrypted octets 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 octets 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 octets 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 octets, 01000111 01101000. All this because everything is done in little-endian order.

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

Key#01234567
000000000
103472561
262514073
347635210
452371064
567013245
641230756
753702164
820167345
946502713
A74625130
B65471302
C37206145
D06431257
E61574032
F40326175
Key#01234567
00x000x000x000x000x000x000x000x00
10x090x6B0xE70x380xB50x1C0xBC0x52
20x250xBC0xB60x9B0xE10xCA0xA00x17
30x980x0A0xED0x9E0x610x870xD60x36
40x4E0xD30xD50xA50x040x360xC60x75
50xE50x010x150x260xBF0xAB0x320xB5
60xF30x620xE10x200xD90x6D0xD20xB8
70xC80x0F0xAC0xA00x730x170xEF0x34
80xBF0xDC0x5A0xC50x150x270x650x10
90x9A0x5C0x9E0xCB0xBF0x8A0x030x05
A0x730xD30xC90x810x7C0x270x8B0x1A
B0xDF0x0D0xB30xAB0x940xD00x4E0x30
C0x2B0x670x430xA20x1A0x3A0xEC0xF8
D0xD80xA80x670x280xDA0x0C0xCF0x9D
E0x240xAD0x1C0x5E0x4A0x760x830xB7
F0x940xF20xC20xB20x410x6F0x6E0xC5
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 octets into characters. This works much like packing tile values in the tile data. Each character is 5 bits from 1 or 2 octet. Everything is little-endian. The last character value is padded to an even 5 bits. The values then are printed according to Table 5.

Value01234567
89101112131415
1617181920212223
2425262728293031
Character01234567
89CFHJKL
MNPQTVWX
Y!=$#?-+
Table 5: Polarium Advance character map
  (header octets)
   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 octets)
 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 octet)
  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 octet
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.