Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

1
//
2
//  insn.cpp
3
//  liboffsetfinder64
4
//
5
//  Created by tihmstar on 09.03.18.
6
//  Copyright © 2018 tihmstar. All rights reserved.
7
//
8

9
#define LOCAL_FILENAME "insn.cpp"
10

11
#include "all_liboffsetfinder.hpp"
12
#include "insn.hpp"
13
#include "exception.hpp"
14

15
using namespace tihmstar::patchfinder64;
16

17
insn::insn(segment_t segments, loc_t p, segtype segType) : _segments(segments), _segtype(segType){
18
    std::sort(_segments.begin(),_segments.end(),[ ]( const text_t& lhs, const text_t& rhs){
19
        return lhs.base < rhs.base;
20
    });
21
    if (_segtype != kText_and_Data) {
22
        _segments.erase(std::remove_if(_segments.begin(), _segments.end(), [&](const text_t obj){
23
            return (!obj.isExec) == (_segtype == kText_only);
24
        }));
25
    }
26
    if (p == 0) {
27
        p = _segments.at(0).base;
28
    }
29
    for (int i=0; i<_segments.size(); i++){
30
        auto seg = _segments[i];
31
        if ((loc_t)seg.base <= p && p < (loc_t)seg.base+seg.size){
32
            _p = {p,i};
33
            return;
34
        }
35
    }
36
    throw out_of_range("initializing insn with out of range location");
37
}
38

39
insn::insn(const insn &cpy, loc_t p){
40
    _segments = cpy._segments;
41
    _segtype = cpy._segtype;
42
    if (p==0) {
43
        _p = cpy._p;
44
    }else{
45
        for (int i=0; i<_segments.size(); i++){
46
            auto seg = _segments[i];
47
            if ((loc_t)seg.base <= p && p < (loc_t)seg.base+seg.size){
48
                _p = {p,i};
49
                return;
50
            }
51
        }
52
        throw out_of_range("initializing insn with out of range location");
53
    }
54
}
55

56
insn &insn::operator++(){
57
    _p.first+=4;
58
    if (_p.first >=_segments[_p.second].base+_segments[_p.second].size){
59
        if (_p.second+1 < _segments.size()) {
60
            _p.first = _segments[++_p.second].base;
61
        }else{
62
            _p.first-=4;
63
            throw out_of_range("overflow");
64
        }
65
    }
66
    return *this;
67
}
68

69
insn &insn::operator--(){
70
    _p.first-=4;
71
    if (_p.first < _segments[_p.second].base){
72
        if (_p.second-1 >0) {
73
            --_p.second;
74
            _p.first = _segments[_p.second].base+_segments[_p.second].size;
75
        }else{
76
            _p.first+=4;
77
            throw out_of_range("underflow");
78
        }
79
    }
80
    return *this;
81
}
82

83
insn insn::operator+(int i){
84
    insn cpy(*this);
85
    if (i>0) {
86
        while (i--)
87
            ++cpy;
88
    }else{
89
        while (i++)
90
            --cpy;
91
    }
92
    return cpy;
93
}
94

95
insn insn::operator-(int i){
96
    return this->operator+(-i);
97
}
98

99
insn &insn::operator+=(int i){
100
    if (i>0) {
101
        while (i-->0)
102
            this->operator++();
103
    }else{
104
        while (i++>0)
105
            this->operator--();
106
    }
107
    return *this;
108
}
109

110
insn &insn::operator-=(int i){
111
    return this->operator+=(-i);
112
}
113

114
insn &insn::operator=(loc_t p){
115
    for (int i=0; i<_segments.size(); i++){
116
        auto seg = _segments[i];
117
        if ((loc_t)seg.base <= p && p < (loc_t)seg.base+seg.size){
118
            _p = {p,i};
119
            return *this;
120
        }
121
    }
122
    throw out_of_range("initializing insn with out of range location");
123
}
124

125
#pragma mark reference manual helpers
126
__attribute__((always_inline)) static int64_t signExtend64(uint64_t v, int vSize){
127
    uint64_t e = (v & 1 << (vSize-1))>>(vSize-1);
128
    for (int i=vSize; i<64; i++)
129
        v |= e << i;
130
    return v;
131
}
132

133
__attribute__((always_inline)) static int highestSetBit(uint64_t x){
134
    for (int i=63; i>=0; i--) {
135
        if (x & ((uint64_t)1<<i))
136
            return i;
137
    }
138
    return -1;
139
}
140

141
__attribute__((always_inline)) static int lowestSetBit(uint64_t x){
142
    for (int i=0; i<=63; i++) {
143
        if (x & (1<<i))
144
            return i;
145
    }
146
    return 64;
147
}
148

149
__attribute__((always_inline)) static uint64_t replicate(uint64_t val, int bits){
150
    uint64_t ret = val;
151
    unsigned shift;
152
    for (shift = bits; shift < 64; shift += bits) {    // XXX actually, it is either 32 or 64
153
        ret |= (val << shift);
154
    }
155
    return ret;
156
}
157

158
__attribute__((always_inline)) static uint64_t ones(uint64_t n){
159
    uint64_t ret = 0;
160
    while (n--) {
161
        ret <<=1;
162
        ret |= 1;
163
    }
164
    return ret;
165
}
166

167
__attribute__((always_inline)) static uint64_t ROR(uint64_t x, int shift, int len){
168
    while (shift--) {
169
        x |= (x & 1) << len;
170
        x >>=1;
171
    }
172
    return x;
173
}
174

175
static inline uint64_t ror(uint64_t elt, unsigned size)
176
{
177
    return ((elt & 1) << (size-1)) | (elt >> 1);
178
}
179

180
static inline uint64_t AArch64_AM_decodeLogicalImmediate(uint64_t val, unsigned regSize)
181
{
182
    // Extract the N, imms, and immr fields.
183
    unsigned N = (val >> 12) & 1;
184
    unsigned immr = (val >> 6) & 0x3f;
185
    unsigned imms = val & 0x3f;
186
    unsigned i;
187
    
188
    // assert((regSize == 64 || N == 0) && "undefined logical immediate encoding");
189
//    int len = 31 - countLeadingZeros((N << 6) | (~imms & 0x3f));
190
    int len = highestSetBit( (uint64_t)((N<<6) | ((~imms) & 0b111111)) );
191

192
    // assert(len >= 0 && "undefined logical immediate encoding");
193
    unsigned size = (1 << len);
194
    unsigned R = immr & (size - 1);
195
    unsigned S = imms & (size - 1);
196
    // assert(S != size - 1 && "undefined logical immediate encoding");
197
    uint64_t pattern = (1ULL << (S + 1)) - 1;
198
    for (i = 0; i < R; ++i)
199
        pattern = ror(pattern, size);
200
    
201
    // Replicate the pattern to fill the regSize.
202
    while (size != regSize) {
203
        pattern |= (pattern << size);
204
        size *= 2;
205
    }
206
    
207
    return pattern;
208
}
209

210
__attribute__((always_inline)) static std::pair<int64_t, int64_t> DecodeBitMasks(uint64_t immN, uint8_t imms, uint8_t immr, bool immediate){
211
    uint64_t tmask = 0, wmask = 0;
212
    int8_t levels = 0; //6bit
213

214
    int len = highestSetBit( (uint64_t)((immN<<6) | ((~imms) & 0b111111)) );
215
    assure(len != -1); //reserved value
216
    levels = ones(len);
217

218
    assure(immediate && (imms & levels) != levels); //reserved value
219

220
    uint8_t S = imms & levels;
221
    uint8_t R = immr & levels;
222

223
    uint8_t esize = 1 << len;
224

225
    uint8_t diff = S - R; // 6-bit subtract with borrow
226
    
227
    uint8_t d = (diff & ((1<<len)-1)) << 1;
228
    
229
    uint64_t welem = ones(S + 1);
230
    uint64_t telem = ones(d + 1);
231
    
232
    uint64_t asd = ROR(welem, R, 32);
233
    
234
    wmask = replicate(ROR(welem, R, 32),esize);
235
    tmask = replicate(telem,esize);
236
//#warning TODO incomplete function implementation!
237
    return {wmask,tmask};
238
}
239

240
#pragma mark bridges
241
uint64_t insn::pc(){
242
    return (uint64_t)_p.first;
243
}
244

245
uint32_t insn::value(){
246
    return *(uint32_t*)(_p.first - _segments[_p.second].base + _segments[_p.second].map);
247
}
248

249
uint64_t insn::doublevalue(){
250
    return *(uint64_t*)(_p.first - _segments[_p.second].base + _segments[_p.second].map);
251
}
252

253
#pragma mark static type determinition
254

255
uint64_t insn::deref(segment_t segments, loc_t p){
256
    return insn(segments, p, insn::kText_and_Data).doublevalue();
257
}
258

259
bool insn::is_adrp(uint32_t i){
260
    return BIT_RANGE(i, 24, 28) == 0b10000 && (i>>31);
261
}
262

263
bool insn::is_adr(uint32_t i){
264
    return BIT_RANGE(i, 24, 28) == 0b10000 && !(i>>31);
265
}
266

267
bool insn::is_add(uint32_t i){
268
    return BIT_RANGE(i, 24, 28) == 0b10001;
269
}
270

271
bool insn::is_bl(uint32_t i){
272
    return (i>>26) == 0b100101;
273
}
274

275
bool insn::is_cbz(uint32_t i){
276
    return BIT_RANGE(i, 24, 30) == 0b0110100;
277
}
278

279
bool insn::is_ret(uint32_t i){
280
    return ((0b11111 << 5) | i) == 0b11010110010111110000001111100000;
281
}
282

283
bool insn::is_tbnz(uint32_t i){
284
    return BIT_RANGE(i, 24, 30) == 0b0110111;
285
}
286

287
bool insn::is_br(uint32_t i){
288
    return ((0b11111 << 5) | i) == 0b11010110000111110000001111100000;
289
}
290

291
bool insn::is_ldr(uint32_t i){
292
//#warning TODO recheck this mask
293
    return (((i>>22) | 0b0100000000) == 0b1111100001 && ((i>>10) % 4)) || ((i>>22 | 0b0100000000) == 0b1111100101) || ((i>>23) == 0b00011000);
294
}
295

296
bool insn::is_cbnz(uint32_t i){
297
    return BIT_RANGE(i, 24, 30) == 0b0110101;
298
}
299

300
bool insn::is_movk(uint32_t i){
301
    return BIT_RANGE(i, 23, 30) == 0b11100101;
302
}
303

304
bool insn::is_orr(uint32_t i){
305
    return BIT_RANGE(i, 23, 30) == 0b01100100;
306
}
307

308
bool insn::is_and(uint32_t i){
309
    return BIT_RANGE(i, 23, 30) == 0b00100100; //immediate
310
//    return BIT_RANGE(i, 24, 30) == 0b0001010; //shifted register
311
}
312

313
bool insn::is_tbz(uint32_t i){
314
    return BIT_RANGE(i, 24, 30) == 0b0110110;
315
}
316

317
bool insn::is_ldxr(uint32_t i){
318
    return (BIT_RANGE(i, 24, 29) == 0b001000) && (i >> 31) && BIT_AT(i, 22);
319
}
320

321
bool insn::is_ldrb(uint32_t i){
322
    return BIT_RANGE(i, 21, 31) == 0b00111000010 || //Immediate post/pre -indexed
323
           BIT_RANGE(i, 22, 31) == 0b0011100101  || //Immediate unsigned offset
324
           (BIT_RANGE(i, 21, 31) == 0b00111000011 && BIT_RANGE(i, 10, 11) == 0b10); //Register
325
}
326

327
bool insn::is_str(uint32_t i){
328
//#warning TODO redo this! currently only recognises STR (immediate)
329
    return (BIT_RANGE(i, 22, 29) == 0b11100100) && (i >> 31);
330
}
331

332
bool insn::is_stp(uint32_t i){
333
//#warning TODO redo this! currently only recognises STR (immediate)
334
    return (BIT_RANGE(i, 25, 30) == 0b010100) && !BIT_AT(i, 22);
335
}
336

337
bool insn::is_movz(uint32_t i){
338
    return (BIT_RANGE(i, 23, 30) == 0b10100101);
339
}
340

341
bool insn::is_bcond(uint32_t i){
342
    return (BIT_RANGE(i, 24, 31) == 0b01010100) && !BIT_AT(i, 4);
343
}
344

345
bool insn::is_b(uint32_t i){
346
    return (BIT_RANGE(i, 26, 31) == 0b000101);
347
}
348

349
bool insn::is_nop(uint32_t i){
350
    return (BIT_RANGE(i, 12, 31) == 0b11010101000000110010) && (0b11111 % (1<<5));
351
}
352

353

354
enum insn::type insn::type(){
355
    uint32_t val = value();
356
    if (is_adrp(val))
357
        return adrp;
358
    else if (is_adr(val))
359
        return adr;
360
    else if (is_add(val))
361
        return add;
362
    else if (is_bl(val))
363
        return bl;
364
    else if (is_cbz(val))
365
        return cbz;
366
    else if (is_ret(val))
367
        return ret;
368
    else if (is_tbnz(val))
369
        return tbnz;
370
    else if (is_br(val))
371
        return br;
372
    else if (is_ldr(val))
373
        return ldr;
374
    else if (is_cbnz(val))
375
        return cbnz;
376
    else if (is_movk(val))
377
        return movk;
378
    else if (is_orr(val))
379
        return orr;
380
    else if (is_and(val))
381
        return and_;
382
    else if (is_tbz(val))
383
        return tbz;
384
    else if (is_ldxr(val))
385
        return ldxr;
386
    else if (is_ldrb(val))
387
        return ldrb;
388
    else if (is_str(val))
389
        return str;
390
    else if (is_stp(val))
391
        return stp;
392
    else if (is_movz(val))
393
        return movz;
394
    else if (is_bcond(val))
395
        return bcond;
396
    else if (is_b(val))
397
        return b;
398
    else if (is_nop(val))
399
        return nop;
400

401
    return unknown;
402
}
403

404
enum insn::subtype insn::subtype(){
405
    uint32_t i = value();
406
    if (is_ldr(i)) {
407
        if ((((i>>22) | (1 << 8)) == 0b1111100001) && BIT_RANGE(i, 10, 11) == 0b10)
408
            return st_register;
409
        else if (i>>31)
410
            return st_immediate;
411
        else
412
            return st_literal;
413
    }else if (is_ldrb(i)){
414
        if (BIT_RANGE(i, 21, 31) == 0b00111000011 && BIT_RANGE(i, 10, 11) == 0b10)
415
            return st_register;
416
        else
417
            return st_immediate;
418
    }
419
    return st_general;
420
}
421

422
enum insn::supertype insn::supertype(){
423
    switch (type()) {
424
        case bl:
425
        case cbz:
426
        case cbnz:
427
        case tbnz:
428
        case bcond:
429
        case b:
430
            return sut_branch_imm;
431

432
        default:
433
            return sut_general;
434
    }
435
}
436

437
#pragma mark register
438

439
int64_t insn::imm(){
440
    switch (type()) {
441
        case unknown:
442
            reterror("can't get imm value of unknown instruction");
443
            break;
444
        case adrp:
445
            return ((pc()>>12)<<12) + signExtend64(((((value() % (1<<24))>>5)<<2) | BIT_RANGE(value(), 29, 30))<<12,32);
446
        case adr:
447
            return pc() + signExtend64((BIT_RANGE(value(), 5, 23)<<2) | (BIT_RANGE(value(), 29, 30)), 21);
448
        case add:
449
            return BIT_RANGE(value(), 10, 21) << (((value()>>22)&1) * 12);
450
        case bl:
451
            return pc() + (signExtend64(value() % (1<<26), 25) << 2); //untested
452
        case cbz:
453
        case cbnz:
454
        case tbnz:
455
        case bcond:
456
            return pc() + (signExtend64(BIT_RANGE(value(), 5, 23), 19)<<2); //untested
457
        case movk:
458
        case movz:
459
            return BIT_RANGE(value(), 5, 20);
460
        case ldr:
461
            if(subtype() != st_immediate){
462
                reterror("can't get imm value of ldr that has non immediate subtype");
463
                break;
464
            }
465
            if(BIT_RANGE(value(), 24, 25)){
466
                // Unsigned Offset
467
                return BIT_RANGE(value(), 10, 21) << (value()>>30);
468
            }else{
469
                // Signed Offset
470
                return signExtend64(BIT_RANGE(value(), 12, 21), 9); //untested
471
            }
472
        case ldrb:
473
            if (st_immediate) {
474
                if (BIT_RANGE(value(), 22, 31) == 0b0011100101) { //unsigned
475
                    return BIT_RANGE(value(), 10, 21) << BIT_RANGE(value(), 30, 31);
476
                }else{  //pre/post indexed
477
                    return BIT_RANGE(value(), 12, 20) << BIT_RANGE(value(), 30, 31);
478
                }
479
            }else{
480
                reterror("ldrb must be st_immediate for imm to be defined!");
481
            }
482
        case str:
483
//#warning TODO rewrite this! currently only unsigned offset supported
484
            // Unsigned Offset
485
            return BIT_RANGE(value(), 10, 21) << (value()>>30);
486
        case orr:
487
            return DecodeBitMasks(BIT_AT(value(), 22),BIT_RANGE(value(), 10, 15),BIT_RANGE(value(), 16,21), true).first;
488
        case and_:
489
        {
490
            int64_t val = DecodeBitMasks(BIT_AT(value(), 22),BIT_RANGE(value(), 10, 15),BIT_RANGE(value(), 16,21), true).first;
491
            if (!BIT_AT(value(), 31))
492
                val |= (((uint64_t)1<<32)-1) << 32;
493
            return val;
494
        }
495
        case tbz:
496
            return BIT_RANGE(value(), 5, 18);
497
        case stp:
498
            return signExtend64(BIT_RANGE(value(), 15, 21),7) << (2+(value()>>31));
499
        case b:
500
            return pc() + ((value() % (1<< 26))<<2);
501
        default:
502
            reterror("failed to get imm value");
503
            break;
504
    }
505
    return 0;
506
}
507

508
uint8_t insn::rd(){
509
    switch (type()) {
510
        case unknown:
511
            reterror("can't get rd of unknown instruction");
512
            break;
513
        case adrp:
514
        case adr:
515
        case add:
516
        case movk:
517
        case orr:
518
        case and_:
519
        case movz:
520
            return (value() % (1<<5));
521

522
        default:
523
            reterror("failed to get rd");
524
            break;
525
    }
526
}
527

528
uint8_t insn::rn(){
529
    switch (type()) {
530
        case unknown:
531
            reterror("can't get rn of unknown instruction");
532
            break;
533
        case add:
534
        case ret:
535
        case br:
536
        case orr:
537
        case and_:
538
        case ldxr:
539
        case ldrb:
540
        case str:
541
        case ldr:
542
        case stp:
543
            return BIT_RANGE(value(), 5, 9);
544

545
        default:
546
            reterror("failed to get rn");
547
            break;
548
    }
549
}
550

551
uint8_t insn::rt(){
552
    switch (type()) {
553
        case unknown:
554
            reterror("can't get rt of unknown instruction");
555
            break;
556
        case cbz:
557
        case cbnz:
558
        case tbnz:
559
        case tbz:
560
        case ldxr:
561
        case ldrb:
562
        case str:
563
        case ldr:
564
        case stp:
565
            return (value() % (1<<5));
566

567
        default:
568
            reterror("failed to get rt");
569
            break;
570
    }
571
}
572

573
uint8_t insn::other(){
574
    switch (type()) {
575
        case unknown:
576
            reterror("can't get other of unknown instruction");
577
            break;
578
        case tbz:
579
            return ((value() >>31) << 5) | BIT_RANGE(value(), 19, 23);
580
        case stp:
581
            return BIT_RANGE(value(), 10, 14); //Rt2
582
        case bcond:
583
            return 0; //condition
584
        case ldrb:
585
            if (subtype() == st_register)
586
                reterror("ERROR: unimplemented!");
587
            else
588
                reterror("ldrb must be st_register for this to be defined!");
589
        default:
590
            reterror("failed to get other");
591
            break;
592
    }
593
}
594

595
#pragma mark cast operators
596
insn::operator void*(){
597
    return (void*)(_p.first - _segments[_p.second].base + _segments[_p.second].map);
598
}
599

600
insn::operator loc_t(){
601
    return (loc_t)pc();
602
}
603

604
insn::operator enum type(){
605
    return type();
606
}
607

608
#pragma mark additional functions
609
loc_t tihmstar::patchfinder64::find_literal_ref(segment_t segemts, loc_t pos, int ignoreTimes){
610
    insn adrp(segemts);
611
    uint8_t rd = 0xff;
612
    uint64_t imm = 0;
613
    
614
    try {
615
        for (;;++adrp){
616
            if (adrp == insn::adr) {
617
                if (adrp.imm() == (uint64_t)pos){
618
                    if (ignoreTimes) {
619
                        ignoreTimes--;
620
                        rd = 0xff;
621
                        imm = 0;
622
                        continue;
623
                    }
624
                    return (loc_t)adrp.pc();
625
                }
626
            }else if (adrp == insn::adrp) {
627
                rd = adrp.rd();
628
                imm = adrp.imm();
629
            }else if (adrp == insn::add && rd == adrp.rd()){
630
                if (imm + adrp.imm() == (int64_t)pos){
631
                    if (ignoreTimes) {
632
                        ignoreTimes--;
633
                        rd = 0xff;
634
                        imm = 0;
635
                        continue;
636
                    }
637
                    return (loc_t)adrp.pc();
638
                }
639
            }
640
        }
641
    } catch (std::out_of_range &e) {
642
        return 0;
643
    }
644
    return 0;
645
}
646

647
loc_t tihmstar::patchfinder64::find_rel_branch_source(insn bdst, bool searchUp, int ignoreTimes, int limit){
648
    insn bsrc(bdst);
649

650
    bool hasLimit = (limit);
651
    while (true) {
652
        if (searchUp){
653
            while ((--bsrc).supertype() != insn::sut_branch_imm){
654
                if (hasLimit && !limit--) {
655
                  return 0;
656
                }
657
            }
658
        }else{
659
            while ((++bsrc).supertype() != insn::sut_branch_imm){
660
                if (hasLimit && !limit--) {
661
                  return 0;
662
                }
663
            }
664
        }
665

666
        if (bsrc.imm() == bdst.pc()) {
667
            if (ignoreTimes) {
668
                ignoreTimes--;
669
                continue;
670
            }
671
            return (loc_t)bsrc.pc();
672
        }
673
    }
674
    
675
    //this return is never reached
676
    return 0;
677
}
678

679

680