PwnCollege - RE - Advanced Sprites

Posted on In Views: Disqus:

This level explores trade-offs between adding just a bit of complexity to a software feature (in this case, the cIMG sprite functionality) and its resulting functionality improvement (making the cIMG file smaller!). We might be getting close to optimal cIMG sizes here, and /challenge/cimg will be very demanding!

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int main(int argc, char **argv, char **envp)
{

    struct cimg cimg = { 0 };
    cimg.framebuffer = NULL;
    int won = 1;

    if (argc > 1)
    {
        if (strcmp(argv[1]+strlen(argv[1])-5, ".cimg"))
        {
            printf("ERROR: Invalid file extension!");
            exit(-1);
        }
        dup2(open(argv[1], O_RDONLY), 0);
    }

    read_exact(0, &cimg.header, sizeof(cimg.header), "ERROR: Failed to read header!", -1);

    if (cimg.header.magic_number[0] != 'c' || cimg.header.magic_number[1] != 'I' || cimg.header.magic_number[2] != 'M' || cimg.header.magic_number[3] != 'G')
    {
        puts("ERROR: Invalid magic number!");
        exit(-1);
    }

    if (cimg.header.version != 4)
    {
        puts("ERROR: Unsupported version!");
        exit(-1);
    }

    initialize_framebuffer(&cimg);

    while (cimg.header.remaining_directives--)
    {
        uint16_t directive_code;
        read_exact(0, &directive_code, sizeof(directive_code), "ERROR: Failed to read &directive_code!", -1);

        switch (directive_code)
        {
        case 1:
            handle_1(&cimg);
            break;
        case 2:
            handle_2(&cimg);
            break;
        case 3:
            handle_3(&cimg);
            break;
        case 4:
            handle_4(&cimg);
            break;
        default:
            fprintf(stderr, "ERROR: invalid directive_code %ux\n", directive_code);
            exit(-1);
        }
    }
    display(&cimg, NULL);

    if (cimg.num_pixels != sizeof(desired_output)/sizeof(term_pixel_t))
    {
        won = 0;
    }
    for (int i = 0; i < cimg.num_pixels && i < sizeof(desired_output)/sizeof(term_pixel_t); i++)
    {
        if (cimg.framebuffer[i].str.c != ((term_pixel_t*)&desired_output)[i].str.c)
        {
            won = 0;
        }
        if (
            cimg.framebuffer[i].str.c != ' ' &&
            cimg.framebuffer[i].str.c != '\n' &&
            memcmp(cimg.framebuffer[i].data, ((term_pixel_t*)&desired_output)[i].data, sizeof(term_pixel_t))
        )
        {
            won = 0;
        }
    }

    if (total_data > 285) won = 0;

    if (won) win();

r2 -A -q -c “pdf @ sym.handle_3; pdf @ sym.handle_4” /challenge/cimg

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
            ; CALL XREF from main @ 0x40143e(x)
┌ 337: sym.handle_3 (int64_t arg1, int64_t arg5, int64_t arg6);
│ `- args(rdi, r8, r9) vars(4:sp[0x20..0x23])
# pass
            ; CALL XREF from main @ 0x40142a(x)
┌ 603: sym.handle_4 (int64_t arg1, int64_t arg5, int64_t arg6);
│ `- args(rdi, r8, r9) vars(16:sp[0x1056..0x1078])
│           0x00401c32      f30f1efa       endbr64
│           0x00401c36      4157           push r15
│           0x00401c38      4156           push r14
│           0x00401c3a      4155           push r13
│           0x00401c3c      4154           push r12
│           0x00401c3e      55             push rbp
│           0x00401c3f      53             push rbx
│           0x00401c40      4c8d9c2400..   lea r11, [rsp - 0x40000]
│           ; CODE XREF from sym.handle_4 @ 0x401c56(x)
│       ┌─> 0x00401c48      4881ec0010..   sub rsp, 0x1000
│       ╎   0x00401c4f      830c2400       or dword [rsp], 0
│       ╎   0x00401c53      4c39dc         cmp rsp, r11
│       └─< 0x00401c56      75f0           jne 0x401c48
│           0x00401c58      4883ec48       sub rsp, 0x48
│           0x00401c5c      488d0dad15..   lea rcx, str.ERROR:_Failed_to_read_sprite_render_record_ ; 0x403210 ; "ERROR: Failed to read &sprite_render_record!" ; int64_t arg4
│           0x00401c63      ba09000000     mov edx, 9                  ; size_t nbyte
│           0x00401c68      4183c8ff       or r8d, 0xffffffff          ; -1 ; arg5
│           0x00401c6c      64488b0425..   mov rax, qword fs:[0x28]
│           0x00401c75      4889842438..   mov qword [rsp + 0x40038], rax ; [0x40038:8]=-1
│           0x00401c7d      31c0           xor eax, eax
│           0x00401c7f      4889fb         mov rbx, rdi                ; arg1
│           0x00401c82      488d742416     lea rsi, [var_16h]          ; void *buf
│           0x00401c87      31ff           xor edi, edi                ; int fildes
│           0x00401c89      e86dfaffff     call sym.read_exact
│           0x00401c8e      488d7c241f     lea rdi, [var_1fh]
│           0x00401c93      b900000100     mov ecx, 0x10000
│           0x00401c98      31c0           xor eax, eax
│           0x00401c9a      0fb6542416     movzx edx, byte [var_16h]
│           0x00401c9f      448a542417     mov r10b, byte [var_17h]
│           0x00401ca4      488d74241f     lea rsi, [var_1fh]
│           0x00401ca9      f3ab           rep stosd dword [rdi], eax
│           0x00401cab      448a5c2418     mov r11b, byte [var_18h]
│           0x00401cb0      408a6c2419     mov bpl, byte [var_19h]
│           0x00401cb5      48c1e204       shl rdx, 4
│           0x00401cb9      4801da         add rdx, rbx
│           0x00401cbc      440fb66218     movzx r12d, byte [rdx + 0x18]
│           ; CODE XREF from sym.handle_4 @ 0x401d1c(x)
│       ┌─> 0x00401cc1      4139cc         cmp r12d, ecx
│      ┌──< 0x00401cc4      7e58           jle 0x401d1e
│      │╎   0x00401cc6      440fb64219     movzx r8d, byte [rdx + 0x19]
│      │╎   0x00401ccb      31ff           xor edi, edi
│      │╎   0x00401ccd      4489c0         mov eax, r8d
│      │╎   0x00401cd0      0fafc1         imul eax, ecx
│      │╎   ; CODE XREF from sym.handle_4 @ 0x401d18(x)
│     ┌───> 0x00401cd3      4139f8         cmp r8d, edi
│    ┌────< 0x00401cd6      7e42           jle 0x401d1a
│    │╎│╎   0x00401cd8      4c8b4a20       mov r9, qword [rdx + 0x20]
│    │╎│╎   0x00401cdc      44881486       mov byte [rsi + rax*4], r10b
│    │╎│╎   0x00401ce0      44885c8601     mov byte [rsi + rax*4 + 1], r11b
│    │╎│╎   0x00401ce5      40886c8602     mov byte [rsi + rax*4 + 2], bpl
│    │╎│╎   0x00401cea      4d85c9         test r9, r9
│   ┌─────< 0x00401ced      751b           jne 0x401d0a
│   ││╎│╎   0x00401cef      488b356ade..   mov rsi, qword [obj.stderr] ; obj.stderr__GLIBC_2.2.5
│   ││╎│╎                                                              ; [0x40fb60:8]=0 ; FILE *stream
│   ││╎│╎   0x00401cf6      488d3d4015..   lea rdi, str.ERROR:_attempted_to_render_uninitialized_sprite__n ; 0x40323d ; "ERROR: attempted to render uninitialized sprite!\n" ; const char *s
│   ││╎│╎   0x00401cfd      e8def4ffff     call sym.imp.fputs          ; int fputs(const char *s, FILE *stream)
│   ││╎│╎   0x00401d02      83cfff         or edi, 0xffffffff          ; -1
│   ││╎│╎   0x00401d05      e876f5ffff     call sym.imp.exit           ; void exit(int status)
│   ││╎│╎   ; CODE XREF from sym.handle_4 @ 0x401ced(x)
│   └─────> 0x00401d0a      458a0c01       mov r9b, byte [r9 + rax]
│    │╎│╎   0x00401d0e      ffc7           inc edi
│    │╎│╎   0x00401d10      44884c8603     mov byte [rsi + rax*4 + 3], r9b
│    │╎│╎   0x00401d15      48ffc0         inc rax
│    │└───< 0x00401d18      ebb9           jmp 0x401cd3
│    │ │╎   ; CODE XREF from sym.handle_4 @ 0x401cd6(x)
│    └────> 0x00401d1a      ffc1           inc ecx
│      │└─< 0x00401d1c      eba3           jmp 0x401cc1
│      │    ; CODE XREF from sym.handle_4 @ 0x401cc4(x)
│      └──> 0x00401d1e      4531ff         xor r15d, r15d
│           0x00401d21      488dbc241f..   lea rdi, [rsp + 0x4001f]
│           ; CODE XREF from sym.handle_4 @ 0x401e5e(x)
│       ┌─> 0x00401d29      0fb644241d     movzx eax, byte [var_1dh]
│       ╎   0x00401d2e      4439f8         cmp eax, r15d
│      ┌──< 0x00401d31      0f8e2c010000   jle 0x401e63
│      │╎   0x00401d37      4531d2         xor r10d, r10d
│      │╎   ; CODE XREF from sym.handle_4 @ 0x401e56(x)
│     ┌───> 0x00401d3a      0fb644241c     movzx eax, byte [var_1ch]
│     ╎│╎   0x00401d3f      4439d0         cmp eax, r10d
│    ┌────< 0x00401d42      0f8e13010000   jle 0x401e5b
│    │╎│╎   0x00401d48      0fb6542416     movzx edx, byte [var_16h]
│    │╎│╎   0x00401d4d      4531db         xor r11d, r11d
│    │╎│╎   0x00401d50      48c1e204       shl rdx, 4
│    │╎│╎   0x00401d54      4801da         add rdx, rbx
│    │╎│╎   0x00401d57      8a4219         mov al, byte [rdx + 0x19]
│    │╎│╎   0x00401d5a      410fafc2       imul eax, r10d
│    │╎│╎   0x00401d5e      0244241a       add al, byte [var_1ah]
│    │╎│╎   0x00401d62      440fb6e0       movzx r12d, al
│    │╎│╎   0x00401d66      8a4218         mov al, byte [rdx + 0x18]
│    │╎│╎   0x00401d69      410fafc7       imul eax, r15d
│    │╎│╎   0x00401d6d      0244241b       add al, byte [var_1bh]
│    │╎│╎   0x00401d71      0fb6e8         movzx ebp, al
│    │╎│╎   ; CODE XREF from sym.handle_4 @ 0x401e4e(x)
│   ┌─────> 0x00401d74      0fb6442416     movzx eax, byte [var_16h]
│   ╎│╎│╎   0x00401d79      48c1e004       shl rax, 4
│   ╎│╎│╎   0x00401d7d      0fb6441818     movzx eax, byte [rax + rbx + 0x18]
│   ╎│╎│╎   0x00401d82      4439d8         cmp eax, r11d
│  ┌──────< 0x00401d85      0f8ec8000000   jle 0x401e53
│  │╎│╎│╎   0x00401d8b      4531ed         xor r13d, r13d
│  │╎│╎│╎   ; CODE XREF from sym.handle_4 @ 0x401e44(x)
│ ┌───────> 0x00401d8e      0fb6442416     movzx eax, byte [var_16h]
│ ╎│╎│╎│╎   0x00401d93      48c1e004       shl rax, 4
│ ╎│╎│╎│╎   0x00401d97      0fb6441819     movzx eax, byte [rax + rbx + 0x19]
│ ╎│╎│╎│╎   0x00401d9c      4439e8         cmp eax, r13d
│ ────────< 0x00401d9f      0f8ea4000000   jle 0x401e49
│ ╎│╎│╎│╎   0x00401da5      410fafc3       imul eax, r11d
│ ╎│╎│╎│╎   0x00401da9      4401e8         add eax, r13d
│ ╎│╎│╎│╎   0x00401dac      4898           cdqe
│ ╎│╎│╎│╎   0x00401dae      0fb6548422     movzx edx, byte [rsp + rax*4 + 0x22]
│ ╎│╎│╎│╎   0x00401db3      3a54241e       cmp dl, byte [var_1eh]
│ ────────< 0x00401db7      0f8484000000   je 0x401e41
│ ╎│╎│╎│╎   0x00401dbd      44895c240c     mov dword [var_ch], r11d
│ ╎│╎│╎│╎   0x00401dc2      be19000000     mov esi, 0x19               ; 25
│ ╎│╎│╎│╎   0x00401dc7      440fb67306     movzx r14d, byte [rbx + 6]
│ ╎│╎│╎│╎   0x00401dcc      4c8d058313..   lea r8, str.e_38_2__03d__03d__03dm_ce_0m ; 0x403156
│ ╎│╎│╎│╎   0x00401dd3      4489542408     mov dword [var_8h], r10d
│ ╎│╎│╎│╎   0x00401dd8      51             push rcx
│ ╎│╎│╎│╎   0x00401dd9      b919000000     mov ecx, 0x19               ; 25
│ ╎│╎│╎│╎   0x00401dde      52             push rdx
│ ╎│╎│╎│╎   0x00401ddf      0fb6548431     movzx edx, byte [rsp + rax*4 + 0x31]
│ ╎│╎│╎│╎   0x00401de4      52             push rdx
│ ╎│╎│╎│╎   0x00401de5      0fb6548438     movzx edx, byte [rsp + rax*4 + 0x38]
│ ╎│╎│╎│╎   0x00401dea      52             push rdx
│ ╎│╎│╎│╎   0x00401deb      440fb64c843f   movzx r9d, byte [rsp + rax*4 + 0x3f]
│ ╎│╎│╎│╎   0x00401df1      ba01000000     mov edx, 1
│ ╎│╎│╎│╎   0x00401df6      31c0           xor eax, eax
│ ╎│╎│╎│╎   0x00401df8      48897c2420     mov qword [var_20h], rdi
│ ╎│╎│╎│╎   0x00401dfd      e86ef3ffff     call sym.imp.__snprintf_chk
│ ╎│╎│╎│╎   0x00401e02      438d442500     lea eax, [r13 + r12]
│ ╎│╎│╎│╎   0x00401e07      488b7c2420     mov rdi, qword [var_20h]
│ ╎│╎│╎│╎   0x00401e0c      448b5c242c     mov r11d, dword [var_ch]
│ ╎│╎│╎│╎   0x00401e11      99             cdq
│ ╎│╎│╎│╎   0x00401e12      448b542428     mov r10d, dword [var_8h]
│ ╎│╎│╎│╎   0x00401e17      4883c420       add rsp, 0x20
│ ╎│╎│╎│╎   0x00401e1b      41f7fe         idiv r14d
│ ╎│╎│╎│╎   0x00401e1e      0f1007         movups xmm0, xmmword [rdi]
│ ╎│╎│╎│╎   0x00401e21      440faff5       imul r14d, ebp
│ ╎│╎│╎│╎   0x00401e25      428d0432       lea eax, [rdx + r14]
│ ╎│╎│╎│╎   0x00401e29      31d2           xor edx, edx
│ ╎│╎│╎│╎   0x00401e2b      f7730c         div dword [rbx + 0xc]
│ ╎│╎│╎│╎   0x00401e2e      486bd218       imul rdx, rdx, 0x18
│ ╎│╎│╎│╎   0x00401e32      48035310       add rdx, qword [rbx + 0x10]
│ ╎│╎│╎│╎   0x00401e36      0f1102         movups xmmword [rdx], xmm0
│ ╎│╎│╎│╎   0x00401e39      488b4710       mov rax, qword [rdi + 0x10]
│ ╎│╎│╎│╎   0x00401e3d      48894210       mov qword [rdx + 0x10], rax
│ ╎│╎│╎│╎   ; CODE XREF from sym.handle_4 @ 0x401db7(x)
│ ────────> 0x00401e41      41ffc5         inc r13d
│ └───────< 0x00401e44      e945ffffff     jmp 0x401d8e
│  │╎│╎│╎   ; CODE XREF from sym.handle_4 @ 0x401d9f(x)
│ ────────> 0x00401e49      41ffc3         inc r11d
│  │╎│╎│╎   0x00401e4c      ffc5           inc ebp
│  │└─────< 0x00401e4e      e921ffffff     jmp 0x401d74
│  │ │╎│╎   ; CODE XREF from sym.handle_4 @ 0x401d85(x)
│  └──────> 0x00401e53      41ffc2         inc r10d
│    │└───< 0x00401e56      e9dffeffff     jmp 0x401d3a
│    │ │╎   ; CODE XREF from sym.handle_4 @ 0x401d42(x)
│    └────> 0x00401e5b      41ffc7         inc r15d
│      │└─< 0x00401e5e      e9c6feffff     jmp 0x401d29
│      │    ; CODE XREF from sym.handle_4 @ 0x401d31(x)
│      └──> 0x00401e63      488b842438..   mov rax, qword [rsp + 0x40038]
│           0x00401e6b      6448330425..   xor rax, qword fs:[0x28]
│       ┌─< 0x00401e74      7405           je 0x401e7b
│       │   0x00401e76      e845f3ffff     call sym.imp.__stack_chk_fail ; void __stack_chk_fail(void)
│       │   ; CODE XREF from sym.handle_4 @ 0x401e74(x)
│       └─> 0x00401e7b      4881c44800..   add rsp, 0x40048
│           0x00401e82      5b             pop rbx
│           0x00401e83      5d             pop rbp
│           0x00401e84      415c           pop r12
│           0x00401e86      415d           pop r13
│           0x00401e88      415e           pop r14
│           0x00401e8a      415f           pop r15
└           0x00401e8c      c3             ret

in handle_4

平铺 (Tiling/Repeat) 和 色键透明 (Chroma Key / Transparency)

  1. 参数结构： handle_4 现在会读取 9 个字节（0x401c63: mov edx, 9），加上 2 字节的 Opcode，单次渲染指令变成了 11 字节。 [Opcode (2)] [ID] [R] [G] [B] [Base_X] [Base_Y] [Repeat_X] [Repeat_Y] [Trans_Char]
  2. 平铺： 外层多了两个循环：r10d 遍历到 Repeat_X - 1，r15d 遍历到 Repeat_Y - 1。只注册一个 1x1 的基础 Sprite（比如字符 - 或 |），然后仅用一条指令，铺满屏幕边框。
  3. 透明通道 (Transparency)：
1
2
3
0x00401dae  movzx edx, byte [rsp + rax*4 + 0x22]  ; 取出 Sprite 当前像素的字符
0x00401db3  cmp dl, byte [var_1eh]                ; 和 Trans_Char 比较
0x00401db7  je 0x401e41                           ; 如果相等，直接跳过渲染

这意味着我们可以把中间的 figlet 字符画整体打包成一个或几个大型的矩形 Sprite，并把透明字符设为空格 (32)。渲染时，它会自动忽略所有空格。

  • 对于纯色的填充色块/线条：直接提取为 1x1 的 Solid Sprite，利用 Repeat_X 和 Repeat_Y 无限延伸。
  • 对于不规则的 ASCII Art：利用背景镂空特性，提取为 Transparent Sprite，空格直接当作透明度丢弃。
  • **关于换行符 ：校验器不查颜色，我们让它们染成同一颜色被识别为一个的纯色垂直边框。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
import struct
from pwn import *

def extract_pixels_from_elf(binary_path, num_pixels):
    elf = ELF(binary_path, checksec=False)
    try:
        addr = elf.symbols["desired_output"]
    except KeyError:
        addr = 0x404020

    raw = elf.read(addr, num_pixels * 24)
    pixels = []
    for i in range(num_pixels):
        chunk = raw[i * 24 : (i + 1) * 24]
        try:
            r = int(chunk[7:10])
            g = int(chunk[11:14])
            b = int(chunk[15:18])
            c = chunk[19]
            pixels.append((r, g, b, c))
        except ValueError:
            pixels.append((0, 0, 0, 32))
    return pixels

def build_payload():
    binary_path = "/challenge/cimg"
    width = 76
    height = 24
    num_pixels = width * height

    log.info("Fetching raw pixel data from upstream...")
    pixels = extract_pixels_from_elf(binary_path, num_pixels)

    fg_pixels = []
    for y in range(height):
        for x in range(width):
            p = pixels[y * width + x]
            if p[3] not in (32, 10):
                fg_pixels.append({
                    'x': x, 'y': y,
                    'r': p[0], 'g': p[1], 'b': p[2], 'c': p[3]
                })
            elif p[3] == 10: # 换行符
                fg_pixels.append({
                    'x': x, 'y': y,
                    'r': 255, 'g': 255, 'b': 255, 'c': 10
                })

    memo = {}
    def solve(min_x, max_x, min_y, max_y):
        state = (min_x, max_x, min_y, max_y)
        if state in memo: return memo[state]

        subset = [p for p in fg_pixels if min_x <= p['x'] <= max_x and min_y <= p['y'] <= max_y]
        if not subset: return 0, []

        bx = min(p['x'] for p in subset)
        by = min(p['y'] for p in subset)
        b_w = max(p['x'] for p in subset) - bx + 1
        b_h = max(p['y'] for p in subset) - by + 1

        colors = set((p['r'], p['g'], p['b']) for p in subset)

        best_cost = float('inf')
        best_blocks = []

        # 只要区域内颜色单一，就可以作为一个 Render Directive
        if len(colors) == 1:
            chars = set(p['c'] for p in subset)
            # 检查是否是完美的“纯色单一字符”矩阵（例如连串的 '-' 或 '|' 或 '\n'）
            is_solid = len(subset) == b_w * b_h and len(chars) == 1
            if is_solid:
                best_cost = 17 # 5(注册1x1) + 1(数据) + 11(渲染并Tiling)
                best_blocks = [{
                    'type': 'solid',
                    'x': bx, 'y': by, 'w': b_w, 'h': b_h,
                    'r': subset[0]['r'], 'g': subset[0]['g'], 'b': subset[0]['b'],
                    'c': subset[0]['c'],
                    'subset': subset
                }]
            else:
                best_cost = 16 + b_w * b_h # 5(注册) + w*h(数据) + 11(镂空渲染)
                best_blocks = [{
                    'type': 'transparent',
                    'x': bx, 'y': by, 'w': b_w, 'h': b_h,
                    'r': subset[0]['r'], 'g': subset[0]['g'], 'b': subset[0]['b'],
                    'subset': subset
                }]

        # 递归寻找最优切割
        xs = sorted(list(set(p['x'] for p in subset)))
        for split_x in xs[1:]:
            c1, blks1 = solve(bx, split_x - 1, by, by + b_h - 1)
            c2, blks2 = solve(split_x, bx + b_w - 1, by, by + b_h - 1)
            if c1 + c2 < best_cost:
                best_cost = c1 + c2
                best_blocks = blks1 + blks2

        ys = sorted(list(set(p['y'] for p in subset)))
        for split_y in ys[1:]:
            c1, blks1 = solve(bx, bx + b_w - 1, by, split_y - 1)
            c2, blks2 = solve(bx, bx + b_w - 1, split_y, by + b_h - 1)
            if c1 + c2 < best_cost:
                best_cost = c1 + c2
                best_blocks = blks1 + blks2

        memo[state] = (best_cost, best_blocks)
        return best_cost, best_blocks

    log.info("Optimizing via 2D BSP with hardware Tiling and Chroma Key...")
    _, blocks = solve(0, width - 1, 0, height - 1)

    sprites = {}
    renders = []

    for blk in blocks:
        if blk['type'] == 'solid':
            text = bytes([blk['c']])
            bw, bh = 1, 1
            rx, ry = blk['w'], blk['h'] # 启用 Tiling
            trans = 0
        else:
            text_arr = bytearray()
            for y in range(blk['h']):
                for x in range(blk['w']):
                    found = False
                    for p in blk['subset']:
                        if p['x'] == blk['x'] + x and p['y'] == blk['y'] + y:
                            text_arr.append(p['c'])
                            found = True
                            break
                    if not found:
                        text_arr.append(32) # 空格占位
            text = bytes(text_arr)
            bw, bh = blk['w'], blk['h']
            rx, ry = 1, 1
            trans = 32 # 启用 Chroma Key 透明度

        sp_key = (text, bw, bh)
        if sp_key not in sprites:
            sprites[sp_key] = len(sprites)

        renders.append({
            'id': sprites[sp_key],
            'x': blk['x'], 'y': blk['y'],
            'r': blk['r'], 'g': blk['g'], 'b': blk['b'],
            'rx': rx, 'ry': ry, 'trans': trans
        })

    payload = bytearray()
    num_directives = len(sprites) + len(renders)

    # 写入 Version 4 的 Header
    payload += struct.pack("<4sHBBI", b"cIMG", 4, width, height, num_directives)

    # 指令 3
    for (text, bw, bh), sp_id in sprites.items():
        payload += struct.pack("<HBBB", 3, sp_id, bw, bh)
        payload += text

    # 指令 4
    for r in renders:
        payload += struct.pack("<HBBBBBBBBB", 4, r['id'], r['r'], r['g'], r['b'], r['x'], r['y'], r['rx'], r['ry'], r['trans'])

    total_size = len(payload)
    if total_size > 285:
        log.error(f"Still bloated... ({total_size} bytes)")
        return

    log.success(f"Final Size: {total_size} bytes.")

    file_name = "payload.cimg"
    with open(file_name, "wb") as f:
        f.write(payload)

    try:
        p = process([binary_path, file_name])
        print(p.recvall(timeout=2).decode(errors="ignore"))
    except Exception:
        log.warning("Error")

if __name__ == "__main__":
    build_payload()