thumb-asm 0.15.0

An ARM Thumb/Thumb-2 decoder, disassembler, assembler and detour installer in pure safe Rust. Decodes and re-encodes the instruction set against Arm's own architecture reference manuals, relocates instructions, and installs trampolines over live code in a firmware image.
Documentation
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
//! Re-siting one decoded instruction so that it still means the same thing at
//! a new address.
//!
//! This is the primitive under [`crate::detour`], and the reason a detour can
//! be installed over *live* code instead of only over a dead prologue. Moving
//! an instruction into a stub is a byte copy for the great majority of the
//! instruction set and a wrong answer for the rest, because Thumb has three
//! separate ways for an instruction's behaviour to depend on its own address:
//!
//! * a **direct branch** carries a displacement from `PC`, so the same bytes at
//!   a new address branch somewhere else (ARM DDI 0403E.e A7.7.12);
//! * a **pc-relative literal access** — `LDR (literal)`, `ADR`, `LDRD
//!   (literal)`, `LDC` — is based on `Align(PC,4)`, which is Thumb's pc value
//!   (this instruction's address plus four) forced word-aligned (A4.2.2);
//! * a handful of instructions **read `pc` as an ordinary value** (`mov rd,
//!   pc`, `add rd, pc`), so the datum itself changes.
//!
//! This crate has already done the hard half of that work in the decoder: an
//! [`Operand::Target`] is the *resolved absolute address*, not a displacement.
//! So relocation never re-does pc arithmetic — it holds the target still and
//! asks whether the new displacement fits, which is exactly what
//! [`isa::encode`] answers. Everything here that is not that is a refusal, and
//! every refusal names the instruction and carries a stable
//! [`reason`](RelocateError::reason) string.
//!
//! # `Align(PC,4)` does not move linearly
//!
//! The subtle case, and the one worth stating out loud: for the literal forms
//! the base is `Align(PC,4)`, which steps in fours while an instruction address
//! steps in twos. Moving an instruction two bytes changes its displacement by
//! **either zero or four**, never by two. So the tempting
//! `new_offset = old_offset - (to - from)` is wrong at every second halfword,
//! and wrong in a way that still assembles. Recomputing the displacement from
//! the resolved target — as this module does — is right by construction.
//!
//! # Worked example
//!
//! A literal load moved two bytes up still reads the same pool word, and here
//! that happens to leave the bytes identical, because both addresses share one
//! `Align(PC,4)`:
//!
//! ```
//! use thumb_asm::isa;
//! use thumb_asm::relocate::relocate;
//!
//! // `ldr r0, [pc, #8]` at 0x1000 — the pool word is at 0x100c.
//! let image = [0x02, 0x48];
//! let insn = isa::decode_at_with(&image, 0, 0x1000, isa::Target::Union).unwrap();
//! assert_eq!(insn.branch_target(), Some(0x100c));
//!
//! // Two bytes up: Align(PC,4) is unchanged, so the displacement is too.
//! let moved = relocate(&insn, 0x1002).unwrap();
//! assert_eq!(moved.branch_target(), Some(0x100c));
//! assert_eq!(isa::encode_bytes(&moved).unwrap(), vec![0x02, 0x48]);
//!
//! // Four bytes up: Align(PC,4) has stepped, so the displacement shrinks by 4.
//! let moved = relocate(&insn, 0x1004).unwrap();
//! assert_eq!(moved.branch_target(), Some(0x100c));
//! assert_eq!(isa::encode_bytes(&moved).unwrap(), vec![0x01, 0x48]);
//!
//! // Far away, the pool is out of the narrow form's 0..1020 reach.
//! let err = relocate(&insn, 0x9000).unwrap_err();
//! assert_eq!(err.reason(), "out-of-range");
//! assert_eq!(err.mnemonic(), "ldr");
//! ```

use crate::isa::{self, AddrMode, Insn, Mem, Operand, Operands, Reg, Width};
use crate::{encode_b_cond, encode_b_wide, Cond};

/// Whether [`relocate_with`] may re-encode a narrow direct branch in its wide
/// form when the narrow displacement no longer reaches.
///
/// # Why this is a choice and not a default
///
/// A narrow branch out of a relocated stub essentially never reaches: `B` T2
/// spans ±2046 bytes and `B<cond>` T1 spans −256/+254, while a stub lives in
/// whatever free space the image has, typically hundreds of kilobytes from the
/// code it was displaced from. So *some* widening is needed for the feature to
/// work at all — but widening changes the instruction's length, and a caller
/// laying out a fixed-size buffer must be told. [`relocate`] therefore never
/// widens, and the widening form is asked for by name.
///
/// The length change is visible in the returned [`Insn`] itself: [`Insn::len`]
/// and [`Insn::width`] are part of the value, so a caller who accepts a
/// widened instruction cannot fail to see that it is now four bytes.
/// [`crate::detour`] relies on exactly that, and lays its stub out in a single
/// forward pass — widening instruction *n* moves only instructions *n+1*
/// onward, which have not been placed yet, so no fixed-point iteration is
/// needed.
///
/// # What is not widened, and why
///
/// Only direct branches. A narrow `ADR` or `LDR (literal)` is refused rather
/// than widened, because the wide forms reach ±4095 bytes — the same "cannot
/// reach a literal pool from free space" class as ±1020. Widening them would
/// buy nothing and would trade a clear refusal for a slightly later one. A
/// consumer that needs a displaced literal load has to *rewrite* it (copy the
/// pool word next to the stub, or materialise the value with `movw`/`movt`),
/// which is a different operation from relocation and not this module's.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum Widen {
    /// Never change the instruction's length. `relocate(i, to)` guarantees
    /// `out.width == i.width`, hence `out.len() == i.len()`.
    Never,
    /// Re-encode a narrow `B` T2 or `B<cond>` T1 in its wide form (`B.W` T4 /
    /// `B<cond>.W` T3, ±16 MB and ±1 MB) when — and only when — the narrow
    /// displacement no longer reaches. The narrowest encoding that reaches is
    /// always preferred, so this is never a gratuitous four bytes.
    IfNeeded,
}

/// Why an instruction cannot be moved to a given address.
///
/// Every variant names the instruction (`mnemonic`) and the two addresses
/// involved (`from`, `to`), and every variant has a stable machine-readable
/// [`reason`](Self::reason) — a refusal a caller cannot classify is a refusal
/// it has to treat as fatal, and most of these are not.
///
/// The variants split into three kinds, which is the distinction that matters
/// when deciding what to do about one:
///
/// * **Address-independent** — [`ReadsPc`](Self::ReadsPc),
///   [`TableBranch`](Self::TableBranch),
///   [`UnresolvedPcRelative`](Self::UnresolvedPcRelative),
///   [`NotEncodable`](Self::NotEncodable). The instruction cannot be moved
///   anywhere; retrying at another address is pointless.
/// * **Address-dependent** — [`OutOfRange`](Self::OutOfRange),
///   [`ForwardOnlyBranch`](Self::ForwardOnlyBranch),
///   [`LiteralAlignment`](Self::LiteralAlignment). Another destination might
///   work, and for a branch [`Widen::IfNeeded`] often fixes it outright.
/// * **Caller error** — [`Misaligned`](Self::Misaligned).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum RelocateError {
    /// `to` is odd. Every Thumb instruction is halfword aligned (A5.1), so
    /// there is no address to relocate to.
    Misaligned {
        /// The instruction's mnemonic.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The odd address it was asked to move to.
        to: u32,
    },
    /// The instruction reads `pc` as an ordinary value operand — `mov rd, pc`,
    /// `add rd, pc`, `cmp rn, pc`, `str pc, [rn]`, `bx pc`, `ldr rt, [rn, pc]`.
    ///
    /// The datum is the instruction's own address plus four (A4.2.2, A7.3), so
    /// it changes under relocation and nothing in the encoding can compensate.
    /// Such an instruction re-encodes perfectly at any address, which is why
    /// this has to be a refusal here rather than an [`isa::encode`] failure:
    /// the bits are fine, the meaning is not.
    ReadsPc {
        /// The instruction's mnemonic.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
    },
    /// A `CBZ`/`CBNZ` whose target no longer reaches.
    ///
    /// The offset is `ZeroExtend(i:imm5:'0')` — **unsigned** (A7.7.21) — so the
    /// range is 0 to 126 bytes *forward* and there is no backward form at all.
    /// A stub in free space is almost never 0..126 bytes below the target, so
    /// in practice a displaced `CBZ` must be rewritten (as `cmp`/`b<cond>.w`),
    /// not relocated. Reported separately from
    /// [`OutOfRange`](Self::OutOfRange) because "out of range" invites a caller
    /// to try a nearer address, and here the reachable window is one-sided.
    ForwardOnlyBranch {
        /// The instruction's mnemonic, `"cbz"` or `"cbnz"`.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
        /// The branch target, which does not move.
        target: u32,
    },
    /// A `TBB`/`TBH`. Not relocatable at any address.
    ///
    /// The table holds *halfword offsets from the table-branch instruction's
    /// own `PC`*: A7.7.185's operation is
    /// `BranchWritePC(PC + 2*UInt(halfwords))`. So every destination in the
    /// table is measured from the `TBB`, and moving the `TBB` silently moves
    /// all of them — while the table itself, wherever it lives, does not move.
    ///
    /// Nothing in the encoding depends on the address, so [`isa::encode`]
    /// re-encodes a moved `TBB` quite happily. This refusal is the only thing
    /// standing between a caller and a jump table that points into the middle
    /// of unrelated code.
    TableBranch {
        /// The instruction's mnemonic, `"tbb"` or `"tbh"`.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
    },
    /// A pc-relative memory operand this module cannot re-resolve: either no
    /// [`Operand::Target`] accompanies it, or it is indexed or writes back.
    ///
    /// Recomputing a pc-relative displacement needs the resolved absolute
    /// address, and the only way to get one for `[pc, rm]` or `[pc], #imm`
    /// would be to know `pc`'s run-time value — which is the thing that
    /// changed. Both shapes are UNPREDICTABLE in the architecture anyway
    /// (A7.7.44 gives the literal form no index and no writeback), so this
    /// variant is a guard rather than a limitation.
    UnresolvedPcRelative {
        /// The instruction's mnemonic.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
    },
    /// An `Align(PC,4)`-based narrow form whose displacement from the new
    /// address would not be a multiple of four.
    ///
    /// The narrow literal forms scale their immediate by four (`imm8:'00'` in
    /// `LDR (literal)` T1 and `ADR` T1, A7.7.44 / A7.7.7), so a displacement
    /// that is 2 mod 4 has no encoding. A *decoded* instruction can never hit
    /// this — its target is `Align(PC,4)` plus a multiple of four and therefore
    /// word-aligned, and the difference of two word-aligned addresses is always
    /// a multiple of four — so this fires only for a hand-built [`Insn`] whose
    /// [`Operand::Target`] is not word-aligned. It is kept, and named, because
    /// that invariant is exactly the one a sign or alignment slip breaks, and a
    /// bare [`OutOfRange`](Self::OutOfRange) would hide which of the two went
    /// wrong.
    LiteralAlignment {
        /// The instruction's mnemonic.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
        /// The resolved target, which does not move.
        target: u32,
    },
    /// The instruction's displacement no longer fits its encoding.
    ///
    /// This is [`isa::encode`]'s `None`, and the only refusal that is decided
    /// by the encoder rather than by this module: the target is held still and
    /// the new displacement offered to the same encoding the instruction came
    /// from. For a narrow direct branch, [`Widen::IfNeeded`] usually turns this
    /// into a success.
    OutOfRange {
        /// The instruction's mnemonic.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
        /// The resolved target or pool address that no longer reaches, if the
        /// instruction has one.
        ///
        /// `None` when it carries no [`Operand::Target`] — which relocation of
        /// a *decoded* instruction never produces, because every encoder whose
        /// output depends on the instruction's own address derives that
        /// dependence from a resolved target, so an instruction without one
        /// encodes identically at every address and can never come out of
        /// range by moving. The field stays an `Option` rather than reporting
        /// a fabricated address for a hand-built [`Insn`], or for a future
        /// encoding whose range turns on its address by some other route.
        target: Option<u32>,
    },
    /// This crate cannot encode the instruction at all, at any address.
    ///
    /// Checked by re-encoding it *where it already is*: if that fails too, the
    /// displacement was never the problem. A relocated instruction this module
    /// cannot hand back as bytes is one the caller cannot emit, so refusing is
    /// the honest answer — and naming [`Insn::encoding`] says which of a
    /// mnemonic's several encodings was at issue.
    NotEncodable {
        /// The instruction's mnemonic.
        mnemonic: &'static str,
        /// The architectural encoding name it was decoded as.
        encoding: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
    },
    /// An Armv8-M `SG`, whose *address* is its meaning.
    ///
    /// `SG` marks the entry point of a secure gateway, and the Security
    /// Attribution Unit decides whether a call is permitted by the address the
    /// `SG` sits at — it must be the first instruction of a Non-Secure
    /// Callable region (ARM DDI 0553B.y B4.3). Moved anywhere else the
    /// instruction still encodes perfectly and still disassembles as `sg`, and
    /// is no longer a gateway: entry through it stops being permitted, and the
    /// address it vacated stops being guarded.
    ///
    /// This is the same class of refusal as [`ReadsPc`](Self::ReadsPc) — the
    /// bits are fine and the meaning is not — which is why it lives here
    /// rather than surfacing as an [`isa::encode`] failure.
    SecureGateway {
        /// The address it was decoded at, which is the address that matters.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
    },
    /// A rewrite was asked for that clobbers condition flags still in use.
    ///
    /// Returned by [`widen_compare_branch`], which turns a `CBZ`/`CBNZ` into
    /// `CMP` + `B<cond>.W`. `CBZ` writes no flags and `CMP` writes all four,
    /// so the rewrite is only sound where every flag is dead.
    ///
    /// Worth reading `live` rather than only its emptiness: it is common for
    /// this to name **only V**, because every `S`-suffixed logical and shift
    /// operation writes N, Z and C and leaves V alone, so a nearby `ANDS` kills
    /// three of the four and looks as though it killed all of them.
    FlagsLive {
        /// The instruction's mnemonic, `"cbz"` or `"cbnz"`.
        mnemonic: &'static str,
        /// The address it was decoded at.
        from: u32,
        /// The address it was asked to move to.
        to: u32,
        /// Which flags are still live there.
        live: crate::flags::Flags,
    },
}

impl RelocateError {
    /// A stable, machine-readable reason: `"misaligned-destination"`,
    /// `"reads-pc"`, `"forward-only-branch"`, `"pc-relative-table"`,
    /// `"unresolved-pc-relative"`, `"literal-alignment"`, `"out-of-range"`,
    /// `"not-encodable"`, `"secure-gateway"`, `"flags-live"`.
    ///
    /// These strings are part of this module's contract. A consumer that logs
    /// or tests against them — a firmware patcher deciding whether to fall
    /// back to a hand-written stub, say — should not have to parse prose or
    /// match on a non-exhaustive enum.
    pub fn reason(&self) -> &'static str {
        match self {
            RelocateError::Misaligned { .. } => "misaligned-destination",
            RelocateError::ReadsPc { .. } => "reads-pc",
            RelocateError::ForwardOnlyBranch { .. } => "forward-only-branch",
            RelocateError::TableBranch { .. } => "pc-relative-table",
            RelocateError::UnresolvedPcRelative { .. } => "unresolved-pc-relative",
            RelocateError::LiteralAlignment { .. } => "literal-alignment",
            RelocateError::OutOfRange { .. } => "out-of-range",
            RelocateError::NotEncodable { .. } => "not-encodable",
            RelocateError::SecureGateway { .. } => "secure-gateway",
            RelocateError::FlagsLive { .. } => "flags-live",
        }
    }

    /// The mnemonic of the instruction that could not be moved.
    pub fn mnemonic(&self) -> &'static str {
        match *self {
            RelocateError::Misaligned { mnemonic, .. }
            | RelocateError::ReadsPc { mnemonic, .. }
            | RelocateError::ForwardOnlyBranch { mnemonic, .. }
            | RelocateError::TableBranch { mnemonic, .. }
            | RelocateError::UnresolvedPcRelative { mnemonic, .. }
            | RelocateError::LiteralAlignment { mnemonic, .. }
            | RelocateError::OutOfRange { mnemonic, .. }
            | RelocateError::NotEncodable { mnemonic, .. } => mnemonic,
            // `SG` carries no mnemonic field because it can only ever be one
            // instruction: the encoding is a single fixed pattern.
            RelocateError::SecureGateway { .. } => "sg",
            RelocateError::FlagsLive { mnemonic, .. } => mnemonic,
        }
    }

    /// The address the instruction was decoded at.
    pub fn from(&self) -> u32 {
        match *self {
            RelocateError::Misaligned { from, .. }
            | RelocateError::ReadsPc { from, .. }
            | RelocateError::ForwardOnlyBranch { from, .. }
            | RelocateError::TableBranch { from, .. }
            | RelocateError::UnresolvedPcRelative { from, .. }
            | RelocateError::LiteralAlignment { from, .. }
            | RelocateError::OutOfRange { from, .. }
            | RelocateError::NotEncodable { from, .. } => from,
            RelocateError::SecureGateway { from, .. } => from,
            RelocateError::FlagsLive { from, .. } => from,
        }
    }

    /// The address it was asked to move to.
    pub fn to(&self) -> u32 {
        match *self {
            RelocateError::Misaligned { to, .. }
            | RelocateError::ReadsPc { to, .. }
            | RelocateError::ForwardOnlyBranch { to, .. }
            | RelocateError::TableBranch { to, .. }
            | RelocateError::UnresolvedPcRelative { to, .. }
            | RelocateError::LiteralAlignment { to, .. }
            | RelocateError::OutOfRange { to, .. }
            | RelocateError::NotEncodable { to, .. } => to,
            RelocateError::SecureGateway { to, .. } => to,
            RelocateError::FlagsLive { to, .. } => to,
        }
    }

    /// Whether another destination address could succeed where this one did
    /// not.
    ///
    /// `false` for the refusals that are properties of the instruction itself,
    /// so a caller searching for somewhere to put a stub knows when to stop
    /// searching.
    pub fn is_address_dependent(&self) -> bool {
        matches!(
            self,
            RelocateError::Misaligned { .. }
                | RelocateError::ForwardOnlyBranch { .. }
                | RelocateError::LiteralAlignment { .. }
                | RelocateError::OutOfRange { .. }
        )
    }
}

impl core::fmt::Display for RelocateError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(
            f,
            "cannot relocate `{}` from {:#x} to {:#x}: {}",
            self.mnemonic(),
            self.from(),
            self.to(),
            self.reason()
        )?;
        match *self {
            RelocateError::Misaligned { .. } => {
                f.write_str(" (a Thumb instruction is halfword aligned)")
            }
            RelocateError::ReadsPc { .. } => {
                f.write_str(" (the pc value it observes changes with its address)")
            }
            RelocateError::SecureGateway { .. } => {
                f.write_str(" (a secure gateway is identified by the address it sits at)")
            }
            RelocateError::FlagsLive { live, .. } => write!(
                f,
                " (the rewrite writes flags that are still live: {live:?})"
            ),
            RelocateError::ForwardOnlyBranch { target, .. } => write!(
                f,
                " (target {target:#x} is not 0..126 bytes forward; cbz/cbnz has no backward form)"
            ),
            RelocateError::TableBranch { .. } => {
                f.write_str(" (the table holds offsets from this instruction's own pc)")
            }
            RelocateError::UnresolvedPcRelative { .. } => {
                f.write_str(" (no resolved target accompanies the pc-relative operand)")
            }
            RelocateError::LiteralAlignment { target, .. } => write!(
                f,
                " (target {target:#x} is not a multiple of 4 from Align(pc,4))"
            ),
            RelocateError::OutOfRange {
                target: Some(t), ..
            } => write!(f, " (target {t:#x} no longer reaches)"),
            RelocateError::OutOfRange { target: None, .. } => {
                f.write_str(" (the displacement no longer fits)")
            }
            RelocateError::NotEncodable { encoding, .. } => {
                write!(f, " (this crate cannot encode {encoding})")
            }
        }
    }
}

impl std::error::Error for RelocateError {}

/// Produce the instruction that has the same effect at `to` as `insn` has at
/// [`Insn::addr`].
///
/// Width-preserving: the returned instruction is always the same length as
/// `insn`, so a caller can lay out a buffer knowing the sizes up front. A
/// narrow branch that no longer reaches is refused with
/// [`RelocateError::OutOfRange`] rather than silently widened; ask for
/// [`relocate_with`] with [`Widen::IfNeeded`] when widening is wanted.
///
/// Every success re-encodes: the returned instruction has been passed through
/// [`isa::encode`], so [`isa::encode_bytes`] on it cannot fail.
///
/// ```
/// use thumb_asm::isa;
/// use thumb_asm::relocate::relocate;
///
/// // `b 0x1010` (B T2) at 0x1000, and the same branch four bytes later.
/// let insn = isa::decode_at_with(&[0x06, 0xe0], 0, 0x1000, isa::Target::Union).unwrap();
/// assert_eq!(insn.branch_target(), Some(0x1010));
/// let moved = relocate(&insn, 0x1004).unwrap();
/// assert_eq!(moved.branch_target(), Some(0x1010)); // the target did not move
/// assert_eq!(moved.len(), 2); // …and neither did the length
/// assert_eq!(isa::encode_bytes(&moved).unwrap(), vec![0x04, 0xe0]);
/// ```
pub fn relocate(insn: &Insn, to: u32) -> Result<Insn, RelocateError> {
    relocate_with(insn, to, Widen::Never)
}

/// [`relocate`], with control over whether a narrow direct branch may be
/// widened to reach.
///
/// With [`Widen::IfNeeded`] the narrowest encoding that reaches is always
/// chosen, so the result is only four bytes when two will not do. Check
/// [`Insn::len`] on the result; see [`Widen`] for why this is opt-in.
///
/// ```
/// use thumb_asm::isa;
/// use thumb_asm::relocate::{relocate_with, Widen};
///
/// // `b 0x1010` cannot reach 0x1010 from 0x9000 in eleven bits …
/// let insn = isa::decode_at_with(&[0x06, 0xe0], 0, 0x1000, isa::Target::Union).unwrap();
/// assert_eq!(relocate_with(&insn, 0x9000, Widen::Never).unwrap_err().reason(), "out-of-range");
///
/// // … but `b.w` spans ±16 MB, and still branches to 0x1010.
/// let wide = relocate_with(&insn, 0x9000, Widen::IfNeeded).unwrap();
/// assert_eq!(wide.branch_target(), Some(0x1010));
/// assert_eq!((wide.mnemonic, wide.encoding, wide.len()), ("b", "T4", 4));
/// ```
pub fn relocate_with(insn: &Insn, to: u32, widen: Widen) -> Result<Insn, RelocateError> {
    relocate_encoded(insn, to, widen).map(|(moved, _)| moved)
}

/// [`relocate_with`], returning the relocated instruction's little-endian
/// bytes.
///
/// The form most callers want, and the one [`crate::detour`] uses: relocation
/// already had to encode the instruction to know the displacement fits, so
/// asking for the bytes costs nothing and removes an `unwrap` from every call
/// site. Two bytes for a narrow instruction, four for a wide one — in
/// word-invariant order, `hw1` first, via [`isa::encode_bytes`].
///
/// ```
/// use thumb_asm::isa;
/// use thumb_asm::relocate::{relocate_bytes, Widen};
///
/// let insn = isa::decode_at_with(&[0x06, 0xe0], 0, 0x1000, isa::Target::Union).unwrap();
/// let bytes = relocate_bytes(&insn, 0x9000, Widen::IfNeeded).unwrap();
/// assert_eq!(bytes.len(), 4); // widened to `b.w`
/// assert_eq!(isa::decode_at_with(&bytes, 0, 0x9000, isa::Target::Union).unwrap().branch_target(), Some(0x1010));
/// ```
pub fn relocate_bytes(insn: &Insn, to: u32, widen: Widen) -> Result<Vec<u8>, RelocateError> {
    relocate_encoded(insn, to, widen).map(|(_, bytes)| bytes)
}

/// The whole of relocation: the instruction as it should be written at `to`,
/// **and the bytes it encodes to**.
///
/// One function rather than two because deciding that a relocation is possible
/// *is* encoding it — the displacement fits exactly when the encoder says so.
/// Handing the bytes back with the instruction means [`relocate_bytes`] has
/// nothing left that can fail, so there is no second, unreachable encode
/// failure for a caller to wonder about. [`relocate_with`] drops them, which
/// costs one small allocation on a path that is not hot: relocation runs once
/// per displaced instruction, not once per decoded one.
fn relocate_encoded(insn: &Insn, to: u32, widen: Widen) -> Result<(Insn, Vec<u8>), RelocateError> {
    let moved = resite(insn, to)?;
    if let Some(bytes) = isa::encode_bytes(&moved) {
        return Ok((moved, bytes));
    }
    if widen == Widen::IfNeeded {
        if let Some(wide) = widened(insn, to) {
            return Ok(wide);
        }
    }
    Err(encode_failure(insn, to))
}

/// Thumb's `Align(PC,4)`: this instruction's address plus four, forced
/// word-aligned (ARM DDI 0403E.e A4.2.2, A7.3).
fn align_pc(addr: u32) -> u32 {
    addr.wrapping_add(4) & !3
}

/// The instruction as it would be written at `to`, with every address-derived
/// field re-derived — but without asking whether it encodes.
///
/// This is where the refusals that [`isa::encode`] *cannot* see are made:
/// `TBB`, `mov rd, pc` and friends re-encode perfectly at any address and are
/// nonetheless wrong there.
fn resite(insn: &Insn, to: u32) -> Result<Insn, RelocateError> {
    let mnemonic = insn.mnemonic;
    let from = insn.addr;

    if to & 1 != 0 {
        return Err(RelocateError::Misaligned { mnemonic, from, to });
    }
    if matches!(mnemonic, "tbb" | "tbh") {
        return Err(RelocateError::TableBranch { mnemonic, from, to });
    }
    // Checked before anything that inspects operands: `SG` has none, and the
    // reason it cannot move has nothing to do with its encoding, which is a
    // single fixed pattern that re-encodes at any address.
    if mnemonic == "sg" {
        return Err(RelocateError::SecureGateway { from, to });
    }
    if reads_pc(insn) {
        return Err(RelocateError::ReadsPc { mnemonic, from, to });
    }

    // A pc-relative memory operand carries the displacement *syntactically*
    // (`[pc, #imm]`) as well as resolved (`Operand::Target`), and the encoders
    // cross-check the two — so both have to be updated, or the instruction
    // stops encoding at all. See `t16_loadstore::encode`.
    let mut operands = insn.operands;
    if let Some(mem) = pc_mem(insn) {
        if mem.index.is_some() || mem.mode != AddrMode::Offset {
            return Err(RelocateError::UnresolvedPcRelative { mnemonic, from, to });
        }
        let target = match first_target(insn) {
            Some(t) => t,
            None => return Err(RelocateError::UnresolvedPcRelative { mnemonic, from, to }),
        };
        // `Mem` carries the displacement as an unsigned magnitude plus the
        // architecture's `U` bit, because `#0` and `#-0` are distinct
        // encodings (A7.7.50) — so a zero displacement must keep whichever `U`
        // the instruction already had rather than inventing `add: true` and
        // changing the bytes.
        let disp = i64::from(target) - i64::from(align_pc(to));
        let (offset, add) = if disp > 0 {
            (disp as u32, true)
        } else if disp < 0 {
            ((-disp) as u32, false)
        } else {
            (0, mem.add)
        };
        operands = replace_pc_mem(&insn.operands, Mem { offset, add, ..mem });
    }

    // The narrow `Align(PC,4)` forms scale their immediate by four, so a
    // displacement that is 2 mod 4 has no encoding. Named separately from
    // `OutOfRange` because it is the invariant a sign or alignment slip breaks.
    //
    // Written as one `Option` rather than a nested `if let`, here and for `adr`
    // below, because "this is not a scaled literal form" and "it carries no
    // resolved target" lead to the same place — leave it alone — and only the
    // first of the two happens to a decoded instruction.
    let scaled_target = if insn.width == Width::Narrow && is_align_pc_form(insn) {
        first_target(insn)
    } else {
        None
    };
    if let Some(target) = scaled_target {
        if (i64::from(target) - i64::from(align_pc(to))) % 4 != 0 {
            return Err(RelocateError::LiteralAlignment {
                mnemonic,
                from,
                to,
                target,
            });
        }
    }

    // `ADR.W` is two encodings, not one with a sign: T3 adds the immediate to
    // `Align(PC,4)` and T2 subtracts it (A7.7.7), and `Insn::encoding` is what
    // tells `t32_dp_plainimm::encode` which bits to emit. Moving an `adr` past
    // its own label flips which of the two can express it, and re-labelling it
    // here costs nothing — same mnemonic, same operands, same four bytes — so
    // the alternative would be refusing a relocation that is perfectly
    // representable.
    let mut encoding = insn.encoding;
    let adr_target = if mnemonic == "adr" && insn.width == Width::Wide {
        first_target(insn)
    } else {
        None
    };
    if let Some(target) = adr_target {
        encoding = if target >= align_pc(to) { "T3" } else { "T2" };
    }

    Ok(Insn {
        addr: to,
        encoding,
        operands,
        ..*insn
    })
}

/// Classify an [`isa::encode`] failure after [`resite`] has already passed.
fn encode_failure(insn: &Insn, to: u32) -> RelocateError {
    let mnemonic = insn.mnemonic;
    let from = insn.addr;
    // Re-encoding it where it already is separates "does not fit *there*" from
    // "this crate cannot encode this instruction".
    if isa::encode(insn).is_none() {
        return RelocateError::NotEncodable {
            mnemonic,
            encoding: insn.encoding,
            from,
            to,
        };
    }
    if matches!(mnemonic, "cbz" | "cbnz") {
        return RelocateError::ForwardOnlyBranch {
            mnemonic,
            from,
            to,
            target: first_target(insn).unwrap_or(0),
        };
    }
    RelocateError::OutOfRange {
        mnemonic,
        from,
        to,
        target: first_target(insn),
    }
}

/// The wide form of a narrow direct branch at `to`, or `None` if this is not a
/// branch that can be widened or the wide form does not reach either.
///
/// Built by encoding through the crate's own [`encode_b_wide`] /
/// [`encode_b_cond`] and *decoding the result back*, rather than by
/// hand-assembling an [`Insn`]. That way the returned instruction is by
/// construction exactly what [`isa::Decoder`](crate::isa::Decoder) would
/// report for those bytes — `encoding` of `"T4"`/`"T3"`, `explicit_width` set,
/// condition where T3 carries one — and cannot drift from it.
fn widened(insn: &Insn, to: u32) -> Option<(Insn, Vec<u8>)> {
    if insn.width != Width::Narrow || to & 1 != 0 {
        return None;
    }
    let target = first_target(insn)?;
    let bytes: Vec<u8> = match (insn.mnemonic, insn.encoding, insn.cond) {
        // `B` T2, unconditional in its own right. A `cond` here could only have
        // come from an enclosing `IT` block, and `B.W` T4 is UNPREDICTABLE
        // anywhere but last in one (A7.7.12) — so a governed `b` is left for
        // the caller to think about rather than quietly widened.
        ("b", "T2", None) => encode_b_wide(to as usize, target)?.to_vec(),
        // `B<cond>` T1 widens to T3, which carries the condition in its own
        // encoding exactly as T1 does.
        //
        // [`encode_b_cond`] picks the narrowest form that reaches, and its T1
        // window — `-256..=254`, A7.7.12 — is the same test `t16_branch`'s
        // `fit_disp` applies, which is the one that just failed. So it returns
        // four bytes here. The length is not re-checked because it does not
        // need to be: the instruction handed back is whatever `Decoder` reads
        // in these bytes, so its `width` and `len()` describe them either way.
        ("b", "T1", Some(cond)) if cond != Cond::Al => encode_b_cond(to as usize, cond, target)?,
        _ => return None,
    };
    isa::decode_at_with(&bytes, 0, to, isa::Target::Union).map(|wide| (wide, bytes))
}

/// The first [`Operand::Target`], i.e. the resolved branch destination or pool
/// address. Same rule as [`Insn::branch_target`], spelled out here because for
/// a literal access it is a pool address and calling it a branch target would
/// read wrongly.
fn first_target(insn: &Insn) -> Option<u32> {
    insn.operands.as_slice().find_map(|op| match op {
        Operand::Target(t) => Some(t),
        _ => None,
    })
}

/// The instruction's pc-based memory operand, if it has one.
fn pc_mem(insn: &Insn) -> Option<Mem> {
    insn.operands.as_slice().find_map(|op| match op {
        Operand::Mem(m) if m.base == Reg::PC => Some(m),
        _ => None,
    })
}

/// Whether the instruction's target is measured from `Align(PC,4)` rather than
/// from `PC` — the literal accesses and `ADR`.
fn is_align_pc_form(insn: &Insn) -> bool {
    insn.mnemonic == "adr" || pc_mem(insn).is_some()
}

/// `insn.operands` with the pc-based memory operand replaced.
///
/// A whole-list rebuild because [`Operands`] is append-only — it has `push`,
/// `get` and `as_slice`, and no way to assign one slot. That is the right
/// trade for a decoder producing millions of these, and the cost lands here,
/// once.
fn replace_pc_mem(operands: &Operands, mem: Mem) -> Operands {
    operands
        .as_slice()
        .map(|op| match op {
            Operand::Mem(m) if m.base == Reg::PC => Operand::Mem(mem),
            other => other,
        })
        .collect()
}

/// Whether the instruction *reads* `pc` as an ordinary value.
///
/// The rule, stated once: `pc` named anywhere in the operands is a read, except
/// as operand 0 of an instruction whose operand 0 is a destination. That
/// exception is what keeps `mov pc, lr`, `pop {r4, pc}` and `ldr pc, [r0]`
/// relocatable — they *write* pc from a register or from memory, which does not
/// depend on where they are — while `mov r0, pc` and `add r0, pc` are refused.
///
/// [`Insn::writes_pc`] answers a neighbouring but different question and cannot
/// stand in for this: it reports `bx rm` as a pc write, which is true, but `rm`
/// is a *source* there, so `bx pc` (which branches to `Align(PC,4)`, A7.7.20)
/// would be read as relocatable. Hence the local list of mnemonics whose first
/// operand is a source — the stores, the multi-register transfers, the
/// comparisons, and the register branches.
fn reads_pc(insn: &Insn) -> bool {
    let source_first = first_operand_is_source(insn.mnemonic)
        || (destructive_first_operand(insn.mnemonic) && insn.operands.len() == 2);
    insn.operands
        .as_slice()
        .enumerate()
        .any(|(i, op)| match op {
            Operand::Reg(r) => r == Reg::PC && (source_first || i != 0),
            // Always a source: no encoding shifts its destination.
            Operand::RegShifted(r, _) => r == Reg::PC,
            // A pc *base* is the literal form, handled by re-resolving the
            // displacement. A pc *index* has no resolved target to work from.
            Operand::Mem(m) => matches!(m.index, Some((r, _)) if r == Reg::PC),
            // `pc` in a load's register list is a destination (`pop {pc}`); in
            // a store's it is the value being written out.
            Operand::RegList(bits) => source_first && bits & (1 << 15) != 0,
            _ => false,
        })
}

/// Whether operand 0 of this mnemonic is a source rather than a destination.
///
/// The stores, `push`, the multi-register transfers and `srs` name the address
/// or the data first; the comparisons consume both operands; `bx`/`blx
/// (register)`/`bxj` take the branch destination as a source register; and
/// `tbb`/`tbh` take the table base. Mirrors the list in [`Insn::writes_pc`],
/// plus the register branches, which that method deliberately treats the other
/// way round.
/// Whether a two-operand form reads its own first operand as well as writing it.
///
/// The 16-bit data-processing and high-register encodings are destructive:
/// `ADD (register)` T2 is `Rdn = Rdn + Rm` (A5.2.3, A7.7.4), so in
/// `add pc, r0` the `pc` is a *source* — the datum is `PC + R0`, which is the
/// Thumb-1 jump-table dispatch. Judging operand 0 by position alone calls that
/// a pure destination and lets [`relocate`] copy the instruction to a stub,
/// where `PC` is different and every switch case lands at the wrong address.
///
/// `mov` and `mvn` are deliberately absent: their first operand is written and
/// not read, so `mov pc, lr` means the same thing wherever it sits.
fn destructive_first_operand(mnemonic: &str) -> bool {
    matches!(
        mnemonic,
        "add"
            | "adc"
            | "sub"
            | "sbc"
            | "rsb"
            | "and"
            | "orr"
            | "orn"
            | "eor"
            | "bic"
            | "mul"
            | "lsl"
            | "lsr"
            | "asr"
            | "ror"
    )
}

fn first_operand_is_source(mnemonic: &str) -> bool {
    mnemonic.starts_with("str")
        || mnemonic.starts_with("vstr")
        || mnemonic.starts_with("vstm")
        || mnemonic.starts_with("vldm")
        || mnemonic.starts_with("stm")
        || mnemonic.starts_with("srs")
        || mnemonic.starts_with("ldm")
        || mnemonic.starts_with("rfe")
        || matches!(
            mnemonic,
            "push"
                | "vpush"
                | "cmp"
                | "cmn"
                | "tst"
                | "teq"
                | "chka"
                | "bx"
                | "blx"
                | "bxj"
                | "tbb"
                | "tbh"
        )
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::isa::{Decoder, ShiftAmount, ShiftKind};

    /// Decode one instruction from `bytes` as if it lived at `addr`.
    fn at(bytes: &[u8], addr: u32) -> Insn {
        isa::decode_at_with(bytes, 0, addr, isa::Target::Union).expect("test vector must decode")
    }

    /// The bytes a relocated instruction assembles to.
    fn bytes_at(insn: &Insn, to: u32) -> Vec<u8> {
        relocate_bytes(insn, to, Widen::Never).expect("must relocate")
    }

    // ----------------------------------------------------- relocatable cases

    /// The overwhelmingly common case: nothing in the encoding depends on the
    /// address, so only `addr` changes and the bytes are identical.
    #[test]
    fn an_address_independent_instruction_only_changes_its_address() {
        let insn = at(&[0x01, 0x20], 0x1000); // movs r0, #1
        assert_eq!(insn.to_string(), "movs r0, #1");
        let moved = relocate(&insn, 0x9_0000).unwrap();
        assert_eq!(moved.addr, 0x9_0000);
        assert_eq!(moved.operands, insn.operands);
        assert_eq!(bytes_at(&insn, 0x9_0000), vec![0x01, 0x20]);
    }

    /// A direct branch's target is absolute in this crate's vocabulary, so it
    /// does not move; the *displacement* is re-derived, and the instruction is
    /// refused when it no longer fits.
    #[test]
    fn a_narrow_unconditional_branch_keeps_its_target() {
        // `b 0x1010` at 0x1000: imm11 = (0x1010 - 0x1004) / 2 = 6.
        let insn = at(&[0x06, 0xe0], 0x1000);
        assert_eq!((insn.mnemonic, insn.encoding), ("b", "T2"));
        assert_eq!(insn.branch_target(), Some(0x1010));

        // Four bytes later the displacement is four smaller: imm11 = 2.
        let moved = relocate(&insn, 0x1004).unwrap();
        assert_eq!(moved.branch_target(), Some(0x1010));
        assert_eq!(bytes_at(&insn, 0x1004), vec![0x04, 0xe0]);

        // Backwards, too: from 0x1020 the displacement is -0x14, i.e. -10
        // halfwords, which is 0x7F6 in eleven bits.
        assert_eq!(bytes_at(&insn, 0x1020), vec![0xf6, 0xe7]);
        assert_eq!(at(&[0xf6, 0xe7], 0x1020).branch_target(), Some(0x1010));

        // ±2046 bytes is all there is (A7.7.12), so a stub cannot hold one.
        let err = relocate(&insn, 0x9000).unwrap_err();
        assert_eq!(err.reason(), "out-of-range");
        assert!(err.is_address_dependent());
    }

    /// `B<cond>` T1's range is −256/+254, not ±256: the offset is
    /// `SignExtend(imm8:'0')`, so the most positive `imm8` is 127 (+254) while
    /// the most negative is −128 (−256). The asymmetry is real and is pinned
    /// here from both ends.
    #[test]
    fn a_narrow_conditional_branch_has_an_asymmetric_range() {
        // `bhi` at 0x1000 with imm8 = 0x7f: target = 0x1000 + 4 + 254 = 0x1102.
        let insn = at(&[0x7f, 0xd8], 0x1000);
        assert_eq!(insn.mnemonic, "b");
        assert_eq!(insn.cond, Some(Cond::Hi));
        assert_eq!(insn.branch_target(), Some(0x1102));

        // +254 is the last reachable forward displacement …
        assert_eq!(bytes_at(&insn, 0x1000), vec![0x7f, 0xd8]);
        // … and +256, two bytes lower down, is already too far.
        assert_eq!(
            relocate(&insn, 0x0ffe).unwrap_err().reason(),
            "out-of-range"
        );

        // -256 *is* reachable, which +256 is not.
        assert_eq!(bytes_at(&insn, 0x11fe), vec![0x80, 0xd8]);
        // -258 is not.
        assert_eq!(
            relocate(&insn, 0x1200).unwrap_err().reason(),
            "out-of-range"
        );

        // Every accepted relocation still branches to the same place.
        for to in [0x1000, 0x1100, 0x11fe] {
            let moved = relocate(&insn, to).unwrap();
            let bytes = isa::encode_bytes(&moved).unwrap();
            assert_eq!(at(&bytes, to).branch_target(), Some(0x1102), "from {to:#x}");
        }
    }

    /// The test most likely to catch a sign or alignment error: a literal load
    /// moved anywhere must still read *the same pool word*.
    ///
    /// Note what the expected bytes say about `Align(PC,4)`. Moving from 0x1000
    /// to 0x1002 leaves the displacement alone, because both addresses have the
    /// same word-aligned pc; moving to 0x1004 shortens it by four, not by two.
    /// An implementation that subtracted `to - from` from the old displacement
    /// would be wrong at 0x1002 and wrong again at 0x0ffe.
    #[test]
    fn a_literal_load_still_reads_the_same_pool_word() {
        // `ldr r0, [pc, #8]` at 0x1000 — Align(pc,4) = 0x1004, pool at 0x100c.
        let insn = at(&[0x02, 0x48], 0x1000);
        assert_eq!((insn.mnemonic, insn.encoding), ("ldr", "T1"));
        assert_eq!(insn.branch_target(), Some(0x100c));
        assert_eq!(insn.to_string(), "ldr r0, [pc, #8], 0x100c");

        // (destination, expected bytes, expected syntactic displacement)
        let cases = [
            (0x0ffeu32, [0x03u8, 0x48], 12i64), // Align(pc,4) = 0x1000
            (0x1000, [0x02, 0x48], 8),          // Align(pc,4) = 0x1004
            (0x1002, [0x02, 0x48], 8),          // Align(pc,4) = 0x1004 — unchanged
            (0x1004, [0x01, 0x48], 4),          // Align(pc,4) = 0x1008 — stepped by 4
            (0x1006, [0x01, 0x48], 4),
            (0x1008, [0x00, 0x48], 0), // `ldr r0, [pc]`
            (0x100a, [0x00, 0x48], 0), // same Align(pc,4) as 0x1008
        ];
        for (to, want, want_offset) in cases {
            let moved = relocate(&insn, to).unwrap();
            // Both views of the address agree, which is what the encoders
            // cross-check: the resolved pool word …
            assert_eq!(moved.branch_target(), Some(0x100c), "from {to:#x}");
            // … and the syntactic `[pc, #imm]`.
            let mem = pc_mem(&moved).expect("pc-relative");
            assert_eq!(mem.displacement(), want_offset, "from {to:#x}");
            assert_eq!(isa::encode_bytes(&moved).unwrap(), want, "from {to:#x}");
            // And the bytes, decoded where they now live, resolve back to the
            // same word — the property the whole module exists for.
            assert_eq!(at(&want, to).branch_target(), Some(0x100c), "from {to:#x}");
        }

        // 0x100c is the first address whose Align(pc,4) is *above* the pool, so
        // it needs a negative displacement — which T1 cannot encode (imm8 is
        // unsigned, A7.7.44). That is a range refusal, not an alignment one.
        assert_eq!(
            relocate(&insn, 0x100c).unwrap_err().reason(),
            "out-of-range"
        );
    }

    /// The wide literal form is byte-granular and signed (`U` selects add or
    /// subtract, A7.7.44 encoding T2), so it relocates in both directions.
    #[test]
    fn a_wide_literal_load_relocates_in_both_directions() {
        // `ldr.w r0, [pc, #8]` at 0x1000: hw1 = 0xf8df (U = 1, Rn = pc),
        // hw2 = 0x0008 (Rt = r0).
        let insn = at(&[0xdf, 0xf8, 0x08, 0x00], 0x1000);
        assert_eq!((insn.mnemonic, insn.encoding), ("ldr", "T2"));
        assert_eq!(insn.branch_target(), Some(0x100c));

        // Above the pool, the offset goes negative and `U` clears.
        let moved = relocate(&insn, 0x2000).unwrap();
        assert_eq!(moved.branch_target(), Some(0x100c));
        assert_eq!(pc_mem(&moved).unwrap().displacement(), 0x100c - 0x2004);
        assert!(
            !pc_mem(&moved).unwrap().add,
            "U must be clear below the pool"
        );
        let bytes = isa::encode_bytes(&moved).unwrap();
        assert_eq!(bytes[0] & 0x80, 0, "U must be clear for a subtracting form");
        assert_eq!(at(&bytes, 0x2000).branch_target(), Some(0x100c));

        // ±4095 is the immediate's whole range, either way. From a
        // word-aligned target the reachable extremes are multiples of four, so
        // 4092 reaches and 4096 does not.
        assert!(relocate(&insn, 0x2004).is_ok()); // displacement -4092
        assert_eq!(
            relocate(&insn, 0x2008).unwrap_err().reason(), // -4096
            "out-of-range"
        );
        assert!(relocate(&insn, 0x000c).is_ok()); // displacement +4092
        assert_eq!(
            relocate(&insn, 0x0008).unwrap_err().reason(), // +4096
            "out-of-range"
        );
    }

    /// `ADR.W` is two encodings — T3 adds, T2 subtracts — so an `adr` moved
    /// past its own label has to change which one it claims to be, or it stops
    /// encoding for a reason that has nothing to do with range.
    #[test]
    fn a_wide_adr_flips_between_its_adding_and_subtracting_forms() {
        // `adr.w r0, 0x1004` at 0x1000 (T3, imm12 = 0).
        let insn = at(&[0x0f, 0xf2, 0x00, 0x00], 0x1000);
        assert_eq!((insn.mnemonic, insn.encoding), ("adr", "T3"));
        assert_eq!(insn.branch_target(), Some(0x1004));

        // Below the label: still T3, a positive displacement.
        let up = relocate(&insn, 0x0f00).unwrap();
        assert_eq!(up.encoding, "T3");
        assert_eq!(up.branch_target(), Some(0x1004));

        // Above it: T2, and the bytes decode back to the same label.
        let down = relocate(&insn, 0x1ffc).unwrap();
        assert_eq!(down.encoding, "T2");
        let bytes = isa::encode_bytes(&down).unwrap();
        let back = at(&bytes, 0x1ffc);
        assert_eq!((back.mnemonic, back.encoding), ("adr", "T2"));
        assert_eq!(back.branch_target(), Some(0x1004));

        // 4095 bytes is the reach of the 12-bit immediate.
        assert_eq!(
            relocate(&insn, 0x2000).unwrap_err().reason(),
            "out-of-range"
        );
    }

    /// An instruction that writes `pc` from a register or from memory is
    /// address-independent and relocates freely; only *reading* pc is a
    /// problem.
    #[test]
    fn writing_pc_is_relocatable_even_though_reading_it_is_not() {
        for (bytes, text) in [
            (vec![0x70, 0x47], "bx lr"),
            (vec![0x10, 0xbd], "pop {r4, pc}"),
            (vec![0xf7, 0x46], "mov pc, lr"),
        ] {
            let insn = at(&bytes, 0x1000);
            assert_eq!(insn.to_string(), text);
            assert!(insn.writes_pc(), "{text}");
            assert_eq!(bytes_at(&insn, 0x9_0000), bytes, "{text}");
        }
    }

    /// A whole IT block moves together, so its governed instructions are
    /// relocated with the condition `Decoder` filled in — and must still
    /// encode to the same halfwords, since the condition lives in the `IT`,
    /// not in them.
    #[test]
    fn an_it_governed_instruction_relocates_to_the_same_halfword() {
        // it eq · movs r0, #1
        let image = [0x08, 0xbf, 0x01, 0x20];
        let mut d = Decoder::at(&image, 0, 0x1000);
        let it = d.next().unwrap();
        assert_eq!(it.mnemonic, "it");
        let governed = d.next().unwrap();
        assert_eq!(governed.cond, Some(Cond::Eq));
        // `Decoder` clears `sets_flags` inside an IT block, because the narrow
        // encodings specify `setflags = !InITBlock()`.
        assert!(!governed.sets_flags);
        assert_eq!(bytes_at(&governed, 0x9_0002), vec![0x01, 0x20]);
        assert_eq!(bytes_at(&it, 0x9_0000), vec![0x08, 0xbf]);
    }

    // -------------------------------------------------------- refusal cases

    /// `cbz`/`cbnz` branch forward only, 0..126 bytes, unsigned — no backward
    /// form exists (A7.7.21), so a stub in free space can never host one.
    #[test]
    fn cbz_and_cbnz_are_refused_as_forward_only() {
        // `cbz r0, 0x100c` at 0x1000 (offset 8) and the `cbnz` beside it.
        for (bytes, mnemonic) in [([0x20, 0xb1], "cbz"), ([0x20, 0xb9], "cbnz")] {
            let insn = at(&bytes, 0x1000);
            assert_eq!(insn.mnemonic, mnemonic);
            assert_eq!(insn.branch_target(), Some(0x100c));

            let err = relocate(&insn, 0x9_0000).unwrap_err();
            assert_eq!(err.reason(), "forward-only-branch");
            assert_eq!(err.mnemonic(), mnemonic);
            assert_eq!(
                err,
                RelocateError::ForwardOnlyBranch {
                    mnemonic,
                    from: 0x1000,
                    to: 0x9_0000,
                    target: 0x100c,
                }
            );
            // Widening does not help: there is no wide `cbz`.
            assert!(relocate_with(&insn, 0x9_0000, Widen::IfNeeded).is_err());
            // Nor does moving backwards, which is the direction a stub sits in
            // only by accident.
            assert_eq!(
                relocate(&insn, 0x100e).unwrap_err().reason(),
                "forward-only-branch"
            );
        }
    }

    /// `tbb`/`tbh` re-encode perfectly at a new address and are nonetheless
    /// broken there, because the table holds offsets from the instruction's own
    /// pc (A7.7.185). This is the refusal `isa::encode` cannot make.
    #[test]
    fn a_table_branch_is_refused_although_it_re_encodes() {
        // `tbb [r0, r1]`.
        let insn = at(&[0xd0, 0xe8, 0x01, 0xf0], 0x1000);
        assert_eq!(insn.mnemonic, "tbb");

        // The encoder is perfectly happy with it at its new address …
        let naive = Insn {
            addr: 0x9_0000,
            ..insn
        };
        assert!(
            isa::encode(&naive).is_some(),
            "nothing in the bits depends on the address, which is the trap"
        );
        // … and this module refuses it anyway.
        let err = relocate(&insn, 0x9_0000).unwrap_err();
        assert_eq!(err.reason(), "pc-relative-table");
        assert!(!err.is_address_dependent());

        // `tbh [pc, r0, lsl #1]` — the pc-based form, same refusal and not the
        // `reads-pc` one, because the table-branch reason is the larger truth.
        let tbh = at(&[0xdf, 0xe8, 0x10, 0xf0], 0x1000);
        assert_eq!(tbh.mnemonic, "tbh");
        assert_eq!(
            relocate(&tbh, 0x2000).unwrap_err().reason(),
            "pc-relative-table"
        );
    }

    /// Reading `pc` as a value: the datum is the instruction's own address plus
    /// four, so no encoding can compensate.
    #[test]
    fn instructions_that_read_pc_are_refused() {
        for (bytes, text) in [
            (vec![0x78, 0x46], "mov r0, pc"),
            (vec![0x78, 0x44], "add r0, pc"),
            (vec![0x78, 0x45], "cmp r0, pc"),
            (vec![0x78, 0x47], "bx pc"),
        ] {
            let insn = at(&bytes, 0x1000);
            assert_eq!(insn.to_string(), text);
            let err = relocate(&insn, 0x2000).unwrap_err();
            assert_eq!(err.reason(), "reads-pc", "{text}");
            assert!(!err.is_address_dependent(), "{text}");
        }
    }

    /// A pc index rather than a pc base: there is no resolved target to
    /// recompute a displacement from, and the architecture does not define the
    /// form either.
    #[test]
    fn a_pc_indexed_memory_operand_is_refused() {
        // Hand-built, because no encoding produces it: `ldr r0, [r1, pc]`.
        let mut operands = Operands::new();
        operands.push(Operand::Reg(Reg(0)));
        operands.push(Operand::Mem(Mem {
            base: Reg(1),
            index: Some((
                Reg::PC,
                Some(crate::isa::Shift {
                    kind: ShiftKind::Lsl,
                    amount: ShiftAmount::Imm(0),
                }),
            )),
            offset: 0,
            add: true,
            align: 0,
            mode: AddrMode::Offset,
        }));
        let insn = Insn {
            mnemonic: "ldr",
            encoding: "T2",
            addr: 0x1000,
            width: Width::Wide,
            cond: None,
            sets_flags: false,
            explicit_width: false,
            operands,
        };
        assert_eq!(relocate(&insn, 0x2000).unwrap_err().reason(), "reads-pc");
    }

    /// An indexed or writing-back pc-relative operand is refused — and both
    /// shapes come out of *decoded* bytes, not just out of a hand-built
    /// [`Insn`].
    ///
    /// `ldrd rt, rt2, [pc], #imm` and `vst4 {…}, [pc], rm` are UNPREDICTABLE
    /// (A7.7.44 gives the literal forms no index and no writeback), which is
    /// not a promise that they are absent from an image: these are halfwords a
    /// firmware blob can contain and this crate does decode. The displacement
    /// they would need after the move cannot be computed — writeback changes
    /// the base the crate is holding still — so the answer is a named refusal
    /// rather than plausible bytes.
    #[test]
    fn an_indexed_or_writing_back_pc_operand_is_refused() {
        // `ldrd r0, r0, [pc], #-0` — post-indexed, no register index.
        let post = at(&[0x7f, 0xe8, 0x00, 0x00], 0x1000);
        assert_eq!(post.mnemonic, "ldrd");
        assert_eq!(pc_mem(&post).unwrap().mode, AddrMode::PostIndex);
        let err = relocate(&post, 0x2000).unwrap_err();
        assert_eq!(err.reason(), "unresolved-pc-relative");
        assert_eq!(err.mnemonic(), "ldrd");
        assert!(!err.is_address_dependent(), "no address can fix it");

        // `vst4.8 {d0-d3}, [pc], r0` — a register index on a pc base, which is
        // the shape with no resolvable address at all.
        let indexed = at(&[0x0f, 0xf9, 0x00, 0x00], 0x1000);
        let mem = pc_mem(&indexed).unwrap();
        assert!(mem.index.is_some());
        assert_eq!(
            relocate(&indexed, 0x2000).unwrap_err().reason(),
            "unresolved-pc-relative"
        );
    }

    /// Reading `pc` through a shifted-register operand is still reading `pc`.
    ///
    /// `Rm == pc` is UNPREDICTABLE in the shifted-register data-processing
    /// encodings, and decodes anyway — so a relocation that trusted the
    /// register list alone would copy `tst.w r0, pc, lsl #8` into a stub where
    /// the value it tests is a different address.
    #[test]
    fn a_shifted_pc_operand_is_read_as_pc() {
        // tst.w r0, pc, lsl #8 — hw1 0xEA10, hw2 0x2F0F.
        let insn = at(&[0x10, 0xea, 0x0f, 0x2f], 0x1000);
        assert_eq!(insn.to_string(), "tst.w r0, pc, lsl #8");
        assert!(reads_pc(&insn));
        let err = relocate(&insn, 0x2000).unwrap_err();
        assert_eq!(err.reason(), "reads-pc");
        assert!(!err.is_address_dependent());

        // The same instruction over an ordinary register moves byte-identically
        // — it is the `pc`, not the shift, that is the problem.
        let ordinary = at(&[0x10, 0xea, 0x01, 0x2f], 0x1000);
        assert_eq!(ordinary.to_string(), "tst.w r0, r1, lsl #8");
        assert!(!reads_pc(&ordinary));
        assert_eq!(bytes_at(&ordinary, 0x9_0000), vec![0x10, 0xea, 0x01, 0x2f]);
    }

    /// A pc-relative memory operand with no resolved target cannot be
    /// re-based, because re-basing *is* holding the resolved address still.
    #[test]
    fn a_pc_relative_operand_without_a_target_is_refused() {
        let mut operands = Operands::new();
        operands.push(Operand::Reg(Reg(0)));
        operands.push(Operand::Mem(Mem {
            base: Reg::PC,
            index: None,
            offset: 8,
            add: true,
            align: 0,
            mode: AddrMode::Offset,
        }));
        let insn = Insn {
            mnemonic: "ldr",
            encoding: "T1",
            addr: 0x1000,
            width: Width::Narrow,
            cond: None,
            sets_flags: false,
            explicit_width: false,
            operands,
        };
        let err = relocate(&insn, 0x2000).unwrap_err();
        assert_eq!(err.reason(), "unresolved-pc-relative");
        assert!(!err.is_address_dependent());
    }

    /// The alignment invariant, guarded.
    ///
    /// A decoded narrow literal access can never trip this — its target is
    /// `Align(PC,4)` plus a multiple of four, so the displacement from any
    /// other `Align(PC,4)` is a multiple of four as well. The refusal exists
    /// for a hand-built or hand-edited [`Insn`], which is precisely how a sign
    /// or shift slip in a caller's own arithmetic arrives here.
    #[test]
    fn a_narrow_literal_with_a_misaligned_target_is_refused() {
        let insn = at(&[0x02, 0x48], 0x1000); // ldr r0, [pc, #8] -> 0x100c
                                              // Two too high: not a multiple of four from any Align(pc,4).
        let bogus = Insn {
            operands: insn
                .operands
                .as_slice()
                .map(|op| match op {
                    Operand::Target(_) => Operand::Target(0x100e),
                    other => other,
                })
                .collect(),
            ..insn
        };
        let err = relocate(&bogus, 0x1000).unwrap_err();
        assert_eq!(err.reason(), "literal-alignment");
        assert_eq!(
            err,
            RelocateError::LiteralAlignment {
                mnemonic: "ldr",
                from: 0x1000,
                to: 0x1000,
                target: 0x100e,
            }
        );
    }

    /// An odd destination is not an address a Thumb instruction can have.
    #[test]
    fn an_odd_destination_is_refused() {
        let insn = at(&[0x01, 0x20], 0x1000);
        let err = relocate(&insn, 0x2001).unwrap_err();
        assert_eq!(err.reason(), "misaligned-destination");
        assert_eq!(err.to(), 0x2001);
        // Including for a branch that would otherwise widen.
        let branch = at(&[0x06, 0xe0], 0x1000);
        assert_eq!(
            relocate_with(&branch, 0x9001, Widen::IfNeeded)
                .unwrap_err()
                .reason(),
            "misaligned-destination"
        );
    }

    /// An instruction this crate cannot encode is refused with the encoding
    /// named, and is distinguished from one that merely does not reach.
    #[test]
    fn an_unencodable_instruction_is_refused_by_name() {
        let insn = Insn {
            mnemonic: "frobnicate",
            encoding: "T9",
            addr: 0x1000,
            width: Width::Narrow,
            cond: None,
            sets_flags: false,
            explicit_width: false,
            operands: Operands::new(),
        };
        let err = relocate(&insn, 0x2000).unwrap_err();
        assert_eq!(err.reason(), "not-encodable");
        assert_eq!(
            err,
            RelocateError::NotEncodable {
                mnemonic: "frobnicate",
                encoding: "T9",
                from: 0x1000,
                to: 0x2000,
            }
        );
        // Widening cannot rescue it either: there is no target to widen
        // towards, so the refusal is the same one.
        assert_eq!(
            relocate_with(&insn, 0x2000, Widen::IfNeeded).unwrap_err(),
            err
        );
    }

    /// Both shapes of the range message, including the one for an instruction
    /// with no resolved target — see [`RelocateError::OutOfRange`]'s `target`
    /// field for why this crate's own relocation cannot produce it and why the
    /// variant still carries an `Option`.
    #[test]
    fn the_range_message_says_what_no_longer_reaches() {
        let with_target = RelocateError::OutOfRange {
            mnemonic: "b",
            from: 0x1000,
            to: 0x9000,
            target: Some(0x1010),
        };
        assert_eq!(
            with_target.to_string(),
            "cannot relocate `b` from 0x1000 to 0x9000: out-of-range \
             (target 0x1010 no longer reaches)"
        );

        let without_target = RelocateError::OutOfRange {
            mnemonic: "b",
            from: 0x1000,
            to: 0x9000,
            target: None,
        };
        assert_eq!(
            without_target.to_string(),
            "cannot relocate `b` from 0x1000 to 0x9000: out-of-range \
             (the displacement no longer fits)"
        );
    }

    /// `Display` hands a sink's failure back rather than swallowing it or
    /// panicking. A firmware tool may well be formatting into a fixed buffer,
    /// and `core::fmt::Write` is allowed to fail there.
    #[test]
    fn display_propagates_a_write_failure() {
        /// A sink with no room in it.
        struct Full;

        impl core::fmt::Write for Full {
            fn write_str(&mut self, _: &str) -> core::fmt::Result {
                Err(core::fmt::Error)
            }
        }

        let err = RelocateError::Misaligned {
            mnemonic: "movs",
            from: 0x1000,
            to: 0x2001,
        };
        assert!(core::fmt::write(&mut Full, format_args!("{err}")).is_err());
    }

    // -------------------------------------------------------------- widening

    /// `B` T2 widens to `B.W` T4 only when asked, and only when it has to.
    #[test]
    fn widening_an_unconditional_branch_is_opt_in_and_minimal() {
        let insn = at(&[0x06, 0xe0], 0x1000); // b 0x1010

        // In range: the narrow form is kept even with widening allowed.
        let near = relocate_with(&insn, 0x1004, Widen::IfNeeded).unwrap();
        assert_eq!((near.width, near.len()), (Width::Narrow, 2));
        assert_eq!(near.encoding, "T2");

        // Out of range: T4, four bytes, same target, and it decodes back.
        let far = relocate_with(&insn, 0x9000, Widen::IfNeeded).unwrap();
        assert_eq!((far.mnemonic, far.encoding, far.len()), ("b", "T4", 4));
        assert!(far.explicit_width);
        assert_eq!(far.branch_target(), Some(0x1010));
        let bytes = isa::encode_bytes(&far).unwrap();
        assert_eq!(bytes.len(), 4);
        assert_eq!(at(&bytes, 0x9000).branch_target(), Some(0x1010));
        // And the same bytes read by the standalone `B.W` decoder, which
        // measures from the offset it is given.
        assert_eq!(
            crate::encode_b_wide(0x9000, 0x1010)
                .as_ref()
                .map(|b| &b[..]),
            Some(&bytes[..])
        );

        // Beyond ±16 MB even T4 cannot reach, and the original error stands.
        assert_eq!(
            relocate_with(&insn, 0x200_0000, Widen::IfNeeded)
                .unwrap_err()
                .reason(),
            "out-of-range"
        );
    }

    /// `B<cond>` T1 widens to `B<cond>.W` T3, which carries the condition in
    /// its own encoding — so the relocated branch is still conditional, and
    /// still conditional on the same thing.
    #[test]
    fn widening_a_conditional_branch_keeps_its_condition() {
        let insn = at(&[0x7f, 0xd8], 0x1000); // bhi 0x1102
        let far = relocate_with(&insn, 0x9000, Widen::IfNeeded).unwrap();
        assert_eq!((far.mnemonic, far.encoding, far.len()), ("b", "T3", 4));
        assert_eq!(far.cond, Some(Cond::Hi));
        assert_eq!(far.branch_target(), Some(0x1102));

        let bytes = isa::encode_bytes(&far).unwrap();
        let back = crate::decode_b_cond(&bytes, 0).unwrap();
        assert_eq!(back.cond, Cond::Hi);
        assert_eq!(back.len, 4);
        let decoded = at(&bytes, 0x9000);
        assert_eq!(decoded.cond, Some(Cond::Hi));
        assert_eq!(decoded.branch_target(), Some(0x1102));

        // T3 spans ±1 MB and no further: 0x10_0000 still reaches 0x1102, and
        // twice that does not.
        assert!(relocate_with(&insn, 0x10_0000, Widen::IfNeeded).is_ok());
        assert_eq!(
            relocate_with(&insn, 0x20_0000, Widen::IfNeeded)
                .unwrap_err()
                .reason(),
            "out-of-range"
        );
    }

    /// Widening is for direct branches. A `b` made conditional by an enclosing
    /// `IT` is not widened, because `B.W` T4 is UNPREDICTABLE anywhere but last
    /// in an IT block — and neither is a literal access, whose wide form reaches
    /// no further in the way that matters.
    #[test]
    fn widening_is_limited_to_direct_branches() {
        // A `b` T2 governed by an `IT`: same halfword, but `cond` is set.
        let image = [0x08, 0xbf, 0x06, 0xe0]; // it eq · b 0x1014
        let mut d = Decoder::at(&image, 0, 0x1000);
        d.next().unwrap();
        let governed = d.next().unwrap();
        assert_eq!((governed.mnemonic, governed.encoding), ("b", "T2"));
        assert_eq!(governed.cond, Some(Cond::Eq));
        assert_eq!(
            relocate_with(&governed, 0x9000, Widen::IfNeeded)
                .unwrap_err()
                .reason(),
            "out-of-range"
        );

        // A narrow literal load is refused, not widened.
        let ldr = at(&[0x02, 0x48], 0x1000);
        let err = relocate_with(&ldr, 0x9000, Widen::IfNeeded).unwrap_err();
        assert_eq!(err.reason(), "out-of-range");
        assert_eq!(err.mnemonic(), "ldr");

        // And an instruction that is *already* wide has nothing to widen to:
        // `ldr.w r0, [pc, #8]` reaches ±4095 and no further, whatever the
        // caller is willing to spend. The refusal is the same as with
        // `Widen::Never`, which is what says widening was not tried.
        let wide = at(&[0xdf, 0xf8, 0x08, 0x00], 0x1000);
        assert_eq!(wide.width, Width::Wide);
        assert_eq!(
            relocate_with(&wide, 0x9000, Widen::IfNeeded).unwrap_err(),
            relocate_with(&wide, 0x9000, Widen::Never).unwrap_err()
        );
        assert_eq!(
            relocate_with(&wide, 0x9000, Widen::IfNeeded)
                .unwrap_err()
                .reason(),
            "out-of-range"
        );
    }

    /// The contract, over the whole 16-bit encoding space: an instruction that
    /// names no pc-derived operand relocates to *byte-identical* bytes.
    ///
    /// A sweep rather than a list, because that is the invariant the rest of the
    /// module rests on — relocation is a byte copy except where it provably is
    /// not — and because it is the cheapest possible cross-check against the
    /// encoders: any group whose `encode` disagrees with its `decode` about an
    /// address-independent field shows up here as a changed halfword.
    #[test]
    fn address_independent_instructions_relocate_byte_identically() {
        let mut checked = 0usize;
        for hw in 0x0000u16..=0xFFFF {
            if isa::insn_len(hw) != 2 {
                continue;
            }
            let bytes = hw.to_le_bytes();
            let insn = match isa::decode_at_with(&bytes, 0, 0x1000, isa::Target::Union) {
                Some(i) => i,
                None => continue,
            };
            // Only the instructions this module promises nothing about are
            // skipped: anything pc-derived, and anything the crate cannot
            // re-encode where it already is.
            if first_target(&insn).is_some()
                || reads_pc(&insn)
                || pc_mem(&insn).is_some()
                || isa::encode(&insn).is_none()
            {
                continue;
            }
            checked += 1;
            let moved = relocate(&insn, 0x2000);
            assert!(moved.is_ok(), "{insn} ({hw:#06x}) must relocate: {moved:?}");
            let moved = moved.unwrap();
            assert_eq!(moved.addr, 0x2000, "{insn} ({hw:#06x})");
            assert_eq!(
                isa::encode_bytes(&moved).as_deref(),
                Some(&bytes[..]),
                "{insn} ({hw:#06x}) changed under relocation"
            );
        }
        // A floor, so a decoder regression cannot make this test vacuous.
        assert!(checked > 20_000, "only {checked} instructions swept");
    }

    /// Every refusal's reason string, in one place, so a change to one is a
    /// change to this test.
    #[test]
    fn reason_strings_are_stable() {
        let all = [
            (
                RelocateError::Misaligned {
                    mnemonic: "movs",
                    from: 0,
                    to: 1,
                },
                "misaligned-destination",
            ),
            (
                RelocateError::ReadsPc {
                    mnemonic: "mov",
                    from: 0,
                    to: 2,
                },
                "reads-pc",
            ),
            (
                RelocateError::ForwardOnlyBranch {
                    mnemonic: "cbz",
                    from: 0,
                    to: 2,
                    target: 4,
                },
                "forward-only-branch",
            ),
            (
                RelocateError::TableBranch {
                    mnemonic: "tbb",
                    from: 0,
                    to: 2,
                },
                "pc-relative-table",
            ),
            (
                RelocateError::UnresolvedPcRelative {
                    mnemonic: "ldr",
                    from: 0,
                    to: 2,
                },
                "unresolved-pc-relative",
            ),
            (
                RelocateError::LiteralAlignment {
                    mnemonic: "ldr",
                    from: 0,
                    to: 2,
                    target: 6,
                },
                "literal-alignment",
            ),
            (
                RelocateError::OutOfRange {
                    mnemonic: "b",
                    from: 0,
                    to: 2,
                    target: Some(4),
                },
                "out-of-range",
            ),
            (
                RelocateError::NotEncodable {
                    mnemonic: "x",
                    encoding: "T1",
                    from: 0,
                    to: 2,
                },
                "not-encodable",
            ),
        ];
        for (err, reason) in all {
            assert_eq!(err.reason(), reason);
            // Every message names the instruction and both addresses.
            let text = err.to_string();
            assert!(text.contains(err.mnemonic()), "{text}");
            assert!(text.contains(reason), "{text}");
        }
    }

    /// Hand-derived vectors, deliberately *not* driven by `reads_pc`.
    ///
    /// The sweep above asks `reads_pc` which instructions to skip, so it can
    /// only ever confirm that predicate's own opinion of itself — which is how
    /// `add pc, rN` was relocated silently for as long as it was. These vectors
    /// come from the encoding diagrams instead: `ADD (register)` T2 is
    /// `Rdn = Rdn + Rm` (A7.7.4), so `add pc, rN` reads `pc` and its value
    /// changes the moment it moves. It is the Thumb-1 jump-table dispatch, and
    /// relocating it sends every switch case to the wrong address.
    #[test]
    fn a_destructive_first_operand_reads_pc_and_cannot_be_relocated() {
        // `add pc, rM` for every M: `0100 0100 1 Rm(4) 111`.
        for m in 0..16u16 {
            let hw = 0x4487 | (m << 3);
            // `decode_at_with(bytes, 0, 0x102, …)`: offset zero into a
            // two-byte slice, *addressed* at 0x102. Passing 0x102 as the offset
            // reads past the end, yields `None`, and would make every assertion
            // below unreachable — the vacuous-sweep shape this file is supposed
            // to be guarding against.
            // `assert!` then `unwrap`, not `unwrap_or_else(|| panic!(…))`:
            // the closure is a function that never runs, and this crate's
            // coverage gate is 100% of functions.
            let decoded =
                crate::isa::decode_at_with(&hw.to_le_bytes(), 0, 0x102, isa::Target::Union);
            assert!(decoded.is_some(), "{hw:#06x} must decode");
            let insn = decoded.unwrap();
            assert_eq!(insn.mnemonic, "add", "{hw:#06x}");
            let err = relocate(&insn, 0x200).expect_err(&format!(
                "{hw:#06x} ({insn}) must not relocate: it reads pc"
            ));
            assert_eq!(err.reason(), "reads-pc", "{hw:#06x} ({insn})");
        }

        // `mov pc, lr` is the counter-case: its first operand is written and
        // never read, so it means the same thing at any address and must stay
        // relocatable. Refusing it would be a silent capability loss.
        let mv = crate::isa::decode_at_with(&0x46F7u16.to_le_bytes(), 0, 0x102, isa::Target::Union)
            .unwrap();
        assert_eq!(mv.mnemonic, "mov");
        assert!(
            relocate(&mv, 0x200).is_ok(),
            "`{mv}` is address-independent and must still relocate"
        );
    }

    // -----------------------------------------------------------------------
    // The two predicates the whole relocator rests on.
    //
    // Mutation testing found both untested in a way coverage could not show:
    // every `||` in `first_operand_is_source` could be flipped to `&&` — which
    // makes the function unconditionally `false`, since no mnemonic starts
    // with two different prefixes at once — and the `RegList` arm of
    // `reads_pc` could be deleted outright, or have its mask shifted to zero,
    // with no test noticing. Both decide whether an instruction may be moved,
    // so a wrong answer writes a broken trampoline into flash.
    // -----------------------------------------------------------------------

    #[test]
    fn first_operand_is_source_recognises_each_family_and_rejects_the_rest() {
        // One per clause, so no single clause can be removed or fused with
        // another and still pass.
        for m in [
            "str", "strb", "strh", "strd", "strex", "vstr", "vstm", "vldm", "stm", "stmdb", "srs",
            "ldm", "ldmdb", "rfe", "push", "vpush", "cmp", "cmn", "tst", "teq", "bx", "blx", "bxj",
            "tbb", "tbh",
        ] {
            assert!(first_operand_is_source(m), "{m} names a source first");
        }
        // Destination-first instructions, including the near-misses: `ldr` is
        // not `ldm`, `sub` is not `srs`, `vldr` is not `vldm`.
        for m in [
            "ldr", "ldrb", "ldrd", "ldrex", "vldr", "mov", "add", "sub", "and", "orr", "eor",
            "mul", "lsl", "asr", "adr", "pop", "b", "bl",
        ] {
            assert!(!first_operand_is_source(m), "{m} names a destination first");
        }
    }

    #[test]
    fn a_register_list_holding_pc_is_read_only_where_pc_is_a_source() {
        let list = |mnemonic: &'static str, bits: u16| Insn {
            mnemonic,
            encoding: "T2",
            addr: 0,
            width: Width::Wide,
            cond: None,
            sets_flags: false,
            explicit_width: false,
            operands: {
                let mut o = Operands::new();
                o.push(Operand::Reg(Reg::SP));
                o.push(Operand::RegList(bits));
                o
            },
        };

        // `stm`/`push` name their data first, so `pc` in the list is a value
        // being read out and the instruction cannot move.
        assert!(reads_pc(&list("stm", 1 << 15)), "stm {{pc}} reads pc");
        assert!(reads_pc(&list("push", 1 << 15)), "push {{pc}} reads pc");

        // The same list without `pc` is fine — this is what a mask shifted to
        // zero, or `&` turned into `|`, would get wrong in the other
        // direction by reporting every list as a pc read.
        assert!(!reads_pc(&list("stm", 0x00FF)), "no pc in the list");
        assert!(!reads_pc(&list("push", 1 << 14)), "lr is not pc");

        // Bit 15 exactly: bit 14 is `lr` and must not be mistaken for it.
        for b in 0..15 {
            assert!(
                !reads_pc(&list("stm", 1 << b)),
                "bit {b} is not pc and must not read as one"
            );
        }

        // A load writes its list, so `pc` there is a destination and the
        // instruction relocates: `pop {r4, pc}` is a return.
        assert!(!reads_pc(&list("pop", (1 << 15) | (1 << 4))));
    }

    // --- byte reproducibility at the zero displacement ---
    //
    // `Mem` carries the displacement as a magnitude plus the architecture's
    // `U` bit precisely because `#0` and `#-0` are distinct encodings. Two
    // guards decide which form comes out at a displacement of exactly zero,
    // and mutation found neither exercised: relocating an instruction that
    // lands on its own literal would change the bytes without changing what
    // it does, which is exactly what the encoding digest exists to notice.

    /// A wide literal load whose `U` is already clear keeps it when the
    /// displacement works out to zero.
    #[test]
    fn a_zero_displacement_keeps_the_u_bit_it_arrived_with() {
        // `ldr.w r0, [pc, #-0]` at 0x1000 — hw1 0xF85F, so `U` is clear.
        let insn = at(&[0x5F, 0xF8, 0x00, 0x00], 0x1000);
        assert!(!pc_mem(&insn).expect("a pc-based memory operand").add);
        // 0x1000 and 0x1002 share `Align(PC, 4)`, so the displacement is zero
        // at both and neither may invent an adding form.
        for to in [0x1000u32, 0x1002] {
            let moved = relocate(&insn, to).expect("address-independent");
            let m = pc_mem(&moved).expect("still a pc-based operand");
            assert_eq!(m.displacement(), 0, "from {to:#x}");
            assert!(!m.add, "U must survive relocation to {to:#x}");
            assert_eq!(
                isa::encode_bytes(&moved).expect("re-encodable"),
                vec![0x5F, 0xF8, 0x00, 0x00],
                "the same four bytes, from {to:#x}"
            );
        }
    }

    /// A wide `adr` that lands exactly on its label stays the adding form.
    ///
    /// T3 adds and T2 subtracts, and at a zero displacement either spells the
    /// same address — so the choice has to be pinned, or the same `adr`
    /// assembles to different bytes depending only on how far it moved.
    #[test]
    fn a_wide_adr_that_lands_exactly_on_its_label_stays_the_adding_form() {
        // `adr.w r0, <pc+0>` at 0x1000, T3 with imm12 == 0.
        let insn = at(&[0x0F, 0xF2, 0x00, 0x00], 0x1000);
        assert_eq!(insn.encoding, "T3");
        let label = insn.branch_target().expect("a resolved label");
        for to in [0x1000u32, 0x1002] {
            let moved = relocate(&insn, to).expect("address-independent");
            assert_eq!(moved.branch_target(), Some(label), "from {to:#x}");
            assert_eq!(moved.encoding, "T3", "the adding form, from {to:#x}");
            assert_eq!(
                isa::encode_bytes(&moved).expect("re-encodable"),
                vec![0x0F, 0xF2, 0x00, 0x00],
                "the same four bytes, from {to:#x}"
            );
        }
    }

    /// Only a *pc-based* memory operand is a literal access.
    ///
    /// `pc_mem` and `replace_pc_mem` both key on `m.base == Reg::PC`, and
    /// mutation showed neither guard exercised with an ordinary base. With
    /// them disabled every memory operand is treated as a literal and has its
    /// displacement re-resolved against the new address — so `ldr r0, [r1,
    /// #4]` would come out of a relocation pointing somewhere else entirely,
    /// while still naming `r1`.
    #[test]
    fn only_a_pc_based_memory_operand_is_a_literal_access() {
        // `ldr r0, [r1, #4]` — an ordinary base register.
        let ordinary = at(&[0x48, 0x68], 0x1000);
        assert!(
            ordinary
                .operands
                .as_slice()
                .any(|o| matches!(o, Operand::Mem(_))),
            "{ordinary} does carry a memory operand"
        );
        assert!(
            pc_mem(&ordinary).is_none(),
            "{ordinary} is not a literal access"
        );
        // So it is address-independent: the same four bytes wherever it goes.
        for to in [0x9000u32, 0x2, 0x1_0000] {
            assert_eq!(
                bytes_at(&ordinary, to),
                vec![0x48, 0x68],
                "{ordinary} moved to {to:#x}"
            );
        }

        // `ldr r0, [pc, #4]` — the same shape with `pc` as the base, and this
        // one *is* a literal access whose displacement has to move.
        let literal = at(&[0x01, 0x48], 0x1000);
        assert!(pc_mem(&literal).is_some(), "{literal} is a literal access");
    }
}

#[cfg(test)]
mod secure_gateway_tests {
    use super::*;
    use crate::isa::{decode_halfwords, Target};

    /// An `SG` is refused, and refused for a reason no caller can work around
    /// by choosing a different address.
    ///
    /// This is the one relocation refusal that is not about range, alignment
    /// or encodability: `SG` re-encodes perfectly anywhere, and moving it is
    /// still wrong. The Security Attribution Unit identifies a gateway by the
    /// address the instruction sits at, so a moved `SG` is no longer a
    /// gateway and the address it left is no longer guarded — a detour over
    /// one would silently close the entry point it was patching.
    #[test]
    fn a_secure_gateway_cannot_be_relocated_to_any_address() {
        let sg = decode_halfwords(0xE97F, 0xE97F, 0x1000, Target::V8M).expect("sg decodes");
        for to in [0x2000u32, 0x1004, 0x0, 0xFFFF_FFFE] {
            let err = relocate(&sg, to).expect_err("sg must never relocate");
            assert_eq!(err.reason(), "secure-gateway", "to {to:#x}");
            assert_eq!(err.mnemonic(), "sg");
            assert_eq!(err.from(), 0x1000);
            assert_eq!(err.to(), to);
            assert!(
                !err.is_address_dependent(),
                "a different address cannot help: the address is the problem"
            );
            assert!(
                err.to_string().contains("address it sits at"),
                "the message should say why, got: {err}"
            );
        }
    }

    /// The refusal is about `SG` specifically, not about Armv8-M: the rest of
    /// the Security Extension relocates normally, because nothing about
    /// `BXNS` or `TT` is tied to the address it occupies.
    #[test]
    fn the_other_security_extension_instructions_still_relocate() {
        for (hw1, hw2) in [(0x4774u16, 0u16), (0xE841, 0xF000)] {
            let insn = decode_halfwords(hw1, hw2, 0x1000, Target::V8M).expect("decodes");
            let moved = relocate(&insn, 0x9000).expect("should relocate");
            assert_eq!(moved.addr, 0x9000);
            assert_eq!(moved.mnemonic, insn.mnemonic);
        }
    }
}

/// Relocate a `CBZ`/`CBNZ` by rewriting it as `CMP` + `B<cond>.W`, when the
/// condition flags are provably dead.
///
/// [`relocate`] refuses these outright
/// ([`ForwardOnlyBranch`](RelocateError::ForwardOnlyBranch)) because the
/// offset is `ZeroExtend(i:imm5:'0')` — unsigned, 0 to 126 bytes forward, with
/// no backward form — so a stub in free space essentially never reaches. The
/// only way to move one is to stop using the encoding:
///
/// ```text
/// cbz rn, target   ->   cmp rn, #0
///                       beq.w target
/// ```
///
/// # Why this needs a proof and not a flag
///
/// `CBZ` writes **no** condition flags; `CMP` writes all four. So the rewrite
/// is a behaviour change unless every flag is already dead at the site, and
/// getting that wrong is the silent kind of wrong — the patched code runs, and
/// a later branch takes the other arm.
///
/// `flags` is what [`crate::flags::live_after`] said about the *original*
/// site, which is the only place the question can be answered: after the move
/// the instruction has no successors yet. This function refuses unless that
/// set is empty. It deliberately does not compute liveness itself, because it
/// receives an `Insn` and liveness is a property of the image around it.
///
/// Note that no `S`-suffixed logical or shift operation makes the flags dead:
/// `ANDS`, `LSLS` and their siblings leave V untouched, and `CMP` writes V.
///
/// # Example
///
/// ```
/// use thumb_asm::flags::{live_after, Flags};
/// use thumb_asm::isa::{self, Target};
/// use thumb_asm::relocate::widen_compare_branch;
///
/// // 0: cbz r0, +8      (branches to 8)
/// // 2: adds r1, r2, r3  (fall-through: writes all four)
/// // 4: bx lr
/// // 6: nop
/// // 8: adds r4, r5, r6  (taken path: writes all four)
/// // 10: bx lr
/// let image = [
///     0x10, 0xb1, 0xd1, 0x18, 0x70, 0x47, 0x00, 0xbf, 0xac, 0x19, 0x70, 0x47,
/// ];
/// let cbz = isa::decode_at_with(&image, 0, 0, Target::Union).unwrap();
/// // Both paths overwrite every flag before anything reads one.
/// let live = live_after(&image, 0, Target::Union, 8);
/// assert_eq!(live, Flags::NONE);
///
/// let bytes = widen_compare_branch(&cbz, 0x9000, live).unwrap();
/// assert_eq!(bytes.len(), 6); // cmp (2) + beq.w (4)
/// ```
pub fn widen_compare_branch(
    insn: &Insn,
    to: u32,
    flags: crate::flags::Flags,
) -> Result<Vec<u8>, RelocateError> {
    let mnemonic = insn.mnemonic;
    let from = insn.addr;
    if !matches!(mnemonic, "cbz" | "cbnz") {
        return Err(RelocateError::NotEncodable {
            mnemonic,
            encoding: insn.encoding,
            from,
            to,
        });
    }
    if to & 1 != 0 {
        return Err(RelocateError::Misaligned { mnemonic, from, to });
    }
    let target = first_target(insn).ok_or(RelocateError::NotEncodable {
        mnemonic,
        encoding: insn.encoding,
        from,
        to,
    })?;
    // The proof, and the whole reason this is a separate entry point.
    if !flags.is_empty() {
        return Err(RelocateError::FlagsLive {
            mnemonic,
            from,
            to,
            live: flags,
        });
    }
    let rn = match insn.operands.get(0) {
        Some(Operand::Reg(r)) => r,
        _ => {
            return Err(RelocateError::NotEncodable {
                mnemonic,
                encoding: insn.encoding,
                from,
                to,
            })
        }
    };
    // `CMP (immediate)` T1 — `0010 1 Rn imm8` — needs a low register.
    if rn.num() > 7 {
        return Err(RelocateError::NotEncodable {
            mnemonic,
            encoding: insn.encoding,
            from,
            to,
        });
    }
    let cmp = 0x2800u16 | (u16::from(rn.num()) << 8);
    // `CBZ` branches when the register *is* zero, so the test is `EQ`;
    // `CBNZ` is `NE`.
    let cond = if mnemonic == "cbz" {
        Cond::Eq
    } else {
        Cond::Ne
    };
    // The `B<cond>` sits two bytes after the `CMP`, and its range is measured
    // from there — not from `to`. The `+ 2` is done in `u32`, where `to`
    // lives, not after a widening `as usize`: a `to` of `0xFFFF_FFFE`
    // (even, so it passes the alignment check above) overflows `to + 2` in the
    // 32-bit Thumb address space whatever the host's pointer width, and a
    // `usize`-space check would only catch it on a 32-bit target while a
    // 64-bit build silently produced a site at `0x1_0000_0000`. A stub cannot
    // live past the top of memory, so this is just another out-of-range
    // destination.
    let branch_site = match to.checked_add(2) {
        Some(s) => s as usize,
        None => {
            return Err(RelocateError::OutOfRange {
                mnemonic,
                from,
                to,
                target: Some(target),
            })
        }
    };
    let branch =
        crate::encode_b_cond(branch_site, cond, target).ok_or(RelocateError::OutOfRange {
            mnemonic,
            from,
            to,
            target: Some(target),
        })?;
    let mut out = Vec::with_capacity(2 + branch.len());
    out.extend_from_slice(&cmp.to_le_bytes());
    out.extend_from_slice(&branch);
    Ok(out)
}

#[cfg(test)]
mod compare_branch_tests {
    use super::*;
    use crate::flags::{live_after, Flags};
    use crate::isa::{decode_at_with, Target};

    /// `cbz r0, 8` at 0; both the fall-through and the taken path overwrite
    /// every flag before reading one, so all four are dead.
    const BOTH_PATHS_CLOBBER: [u8; 12] = [
        0x10, 0xb1, // 0: cbz r0, 8
        0xd1, 0x18, // 2: adds r1, r2, r3
        0x70, 0x47, // 4: bx lr
        0x00, 0xbf, // 6: nop
        0xac, 0x19, // 8: adds r4, r5, r6
        0x70, 0x47, // 10: bx lr
    ];

    #[test]
    fn a_compare_branch_rewrites_when_every_flag_is_dead() {
        let cbz = decode_at_with(&BOTH_PATHS_CLOBBER, 0, 0, Target::Union).expect("cbz");
        let live = live_after(&BOTH_PATHS_CLOBBER, 0, Target::Union, 8);
        assert_eq!(live, Flags::NONE, "the fixture's whole point");

        let bytes = widen_compare_branch(&cbz, 0x9000, live).expect("should rewrite");
        // `cmp r0, #0` then `beq.w`.
        assert_eq!(bytes.len(), 6);
        assert_eq!(&bytes[..2], &0x2800u16.to_le_bytes());

        let cmp = decode_at_with(&bytes, 0, 0x9000, Target::Union).expect("cmp decodes");
        assert_eq!(cmp.mnemonic, "cmp");
        let b = decode_at_with(&bytes, 2, 0x9002, Target::Union).expect("branch decodes");
        assert_eq!(b.mnemonic, "b");
        assert_eq!(b.cond, Some(Cond::Eq), "cbz branches when zero, so EQ");
        assert_eq!(
            b.branch_target(),
            cbz.branch_target(),
            "the rewrite must land on the same target the cbz had"
        );
    }

    /// `CBNZ` becomes `NE`, which is the half of this that is easy to invert.
    #[test]
    fn a_compare_branch_nonzero_becomes_a_not_equal_test() {
        // cbnz r0, 8 — same as above with bit 11 set.
        let mut image = BOTH_PATHS_CLOBBER;
        image[1] = 0xb9;
        let cbnz = decode_at_with(&image, 0, 0, Target::Union).expect("cbnz");
        assert_eq!(cbnz.mnemonic, "cbnz");
        let live = live_after(&image, 0, Target::Union, 8);
        let bytes = widen_compare_branch(&cbnz, 0x9000, live).expect("should rewrite");
        let b = decode_at_with(&bytes, 2, 0x9002, Target::Union).expect("branch");
        assert_eq!(b.cond, Some(Cond::Ne));
    }

    /// The refusal that makes this safe, and the case that makes it subtle.
    ///
    /// An `ANDS` on the fall-through kills N, Z and C but leaves V, so a
    /// model that read `sets_flags` as "all four die" would allow the rewrite
    /// and destroy a V the `bvs` is about to test.
    #[test]
    fn a_live_overflow_flag_alone_is_enough_to_refuse() {
        // 0: cbz r0, 8 / 2: ands r1, r2 / 4: bvs .. / 6: nop
        // 8: adds r4, r5, r6 / 10: bx lr
        let image: [u8; 12] = [
            0x10, 0xb1, 0x11, 0x40, 0xfd, 0xd6, 0x00, 0xbf, 0xac, 0x19, 0x70, 0x47,
        ];
        let cbz = decode_at_with(&image, 0, 0, Target::Union).expect("cbz");
        let live = live_after(&image, 0, Target::Union, 8);
        assert!(live.v, "the bvs reads V and the ands did not write it");

        let err = widen_compare_branch(&cbz, 0x9000, live).expect_err("must refuse");
        assert_eq!(err.reason(), "flags-live");
        assert_eq!(err.mnemonic(), "cbz");
        assert!(
            err.to_string().contains("still live"),
            "the message should say why: {err}"
        );
    }

    /// Anything that is not a compare-branch is not this function's business.
    #[test]
    fn only_a_compare_branch_is_rewritten() {
        let b = decode_at_with(&[0x00, 0xe0], 0, 0, Target::Union).expect("b");
        let err = widen_compare_branch(&b, 0x9000, Flags::NONE).expect_err("not a cbz");
        assert_eq!(err.reason(), "not-encodable");
    }

    /// A `CBZ` whose first operand is not a register has nothing to compare.
    ///
    /// Unreachable from the decoder, which always gives `CBZ` a register
    /// first — this guards the hand-built `Insn` path, which is exactly the
    /// path that produced the `faithful` encoding bug in 0.11.1.
    #[test]
    fn a_compare_branch_without_a_register_is_refused() {
        let cbz = decode_at_with(&BOTH_PATHS_CLOBBER, 0, 0, Target::Union).expect("cbz");
        let mut no_reg = cbz;
        no_reg.operands = [Operand::Target(8)].iter().copied().collect();
        let err = widen_compare_branch(&no_reg, 0x9000, Flags::NONE).expect_err("no register");
        assert_eq!(err.reason(), "not-encodable");

        // ...and the mirror image: a register but no target to branch to.
        let mut no_target = cbz;
        no_target.operands = [Operand::Reg(Reg(0))].iter().copied().collect();
        let err = widen_compare_branch(&no_target, 0x9000, Flags::NONE).expect_err("no target");
        assert_eq!(err.reason(), "not-encodable");
    }

    /// A destination near the top of the address space is refused, not
    /// overflowed.
    ///
    /// `to` is the caller's, and the branch sits at `to + 2`. On a 32-bit
    /// `usize` target that add would overflow for a `to` near `u32::MAX` — a
    /// panic in debug, a wrapped and wrong site in release. It is an
    /// out-of-range destination like any other, because nothing that high can
    /// host a stub.
    #[test]
    fn a_destination_at_the_top_of_memory_is_refused_not_overflowed() {
        let cbz = decode_at_with(&BOTH_PATHS_CLOBBER, 0, 0, Target::Union).expect("cbz");
        let err = widen_compare_branch(&cbz, 0xFFFF_FFFE, Flags::NONE)
            .expect_err("a near-u32::MAX destination cannot host a stub");
        assert_eq!(err.reason(), "out-of-range");
        assert_eq!(err.to(), 0xFFFF_FFFE);
    }

    /// An odd destination has no instruction boundary to land on.
    #[test]
    fn an_odd_destination_is_refused_before_anything_else() {
        let cbz = decode_at_with(&BOTH_PATHS_CLOBBER, 0, 0, Target::Union).expect("cbz");
        let err = widen_compare_branch(&cbz, 0x9001, Flags::NONE).expect_err("odd");
        assert_eq!(err.reason(), "misaligned-destination");
    }

    /// `CMP (immediate)` T1 has a three-bit register field, so a high base
    /// register has no narrow form — and `CBZ` cannot name one anyway, which
    /// is why this is a guard rather than a reachable refusal.
    #[test]
    fn the_rewrite_needs_a_low_register() {
        let cbz = decode_at_with(&BOTH_PATHS_CLOBBER, 0, 0, Target::Union).expect("cbz");
        let mut high = cbz;
        high.operands = [Operand::Reg(Reg(9)), Operand::Target(8)]
            .iter()
            .copied()
            .collect();
        let err = widen_compare_branch(&high, 0x9000, Flags::NONE).expect_err("r9");
        assert_eq!(err.reason(), "not-encodable");
    }

    /// A target the widened branch cannot reach is an out-of-range refusal,
    /// not a silently wrong offset.
    #[test]
    fn a_target_out_of_reach_is_refused() {
        let cbz = decode_at_with(&BOTH_PATHS_CLOBBER, 0, 0, Target::Union).expect("cbz");
        // `B<cond>.W` T3 reaches +-1 MB; put the stub far past that.
        let err = widen_compare_branch(&cbz, 0x40_0000, Flags::NONE).expect_err("too far");
        assert_eq!(err.reason(), "out-of-range");
    }
}