Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / arch-x86.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // $Id: arch-x86.C,v 1.89 2008/09/04 21:06:07 bill Exp $
33
34 // Official documentation used:    - IA-32 Intel Architecture Software Developer Manual (2001 ed.)
35 //                                 - AMD x86-64 Architecture Programmer's Manual (rev 3.00, 1/2002)
36 // Unofficial documentation used:  - www.sandpile.org/ia32
37 //                                 - NASM documentation
38
39 // Note: Unless specified "book" refers to Intel's manual
40
41 #include <assert.h>
42 #include <stdio.h>
43 #include "boost/assign/list_of.hpp"
44 #include "boost/assign/std/vector.hpp"
45 #include "boost/assign/std/set.hpp"
46 #include <map>
47 #include <string>
48 #include "common/h/Types.h"
49 #include "arch.h"
50 #include "util.h"
51 #include "debug.h"
52
53 #include "InstructionDecoder.h"
54 #include "Instruction.h"
55
56 #include "dyninstAPI/src/emit-x86.h"
57 #include "process.h"
58 #include "inst-x86.h"
59 #include "instructionAPI/h/RegisterIDs-x86.h"
60
61 using namespace std;
62 using namespace boost::assign;
63 using namespace Dyninst::InstructionAPI;
64
65 #define MODRM_MOD(x) ((x) >> 6)
66 #define MODRM_RM(x) ((x) & 7)
67 #define MODRM_REG(x) (((x) & (7 << 3)) >> 3)
68 #define MODRM_SET_MOD(x, y) (x) = static_cast<unsigned char>((x) | ((y) << 6))
69 #define MODRM_SET_RM(x, y) (x) = static_cast<unsigned char>((x) | (y))
70 #define MODRM_SET_REG(x, y) (x) = static_cast<unsigned char>((x) | ((y) << 3))
71
72 #define REX_ISREX(x) (((x) >> 4) == 4)
73 #define REX_W(x) ((x) & 0x8)
74 #define REX_R(x) ((x) & 0x4)
75 #define REX_X(x) ((x) & 0x2)
76 #define REX_B(x) ((x) & 0x1)
77
78 #define REX_INIT(x) ((x) = 0x40)
79 #define REX_SET_W(x, v) ((x) = static_cast<unsigned char>((x) | ((v) ? 0x8 : 0)))
80 #define REX_SET_R(x, v) ((x) = static_cast<unsigned char>((x) | ((v) ? 0x4 : 0)))
81 #define REX_SET_X(x, v) ((x) = static_cast<unsigned char>((x) | ((v) ? 0x2 : 0)))
82 #define REX_SET_B(x, v) ((x) = static_cast<unsigned char>((x) | ((v) ? 0x1 : 0)))
83
84 Address get_immediate_operand(instruction *instr)
85 {
86     ia32_memacc mac[3];
87     ia32_condition cond;
88     ia32_locations loc;
89     ia32_instruction detail(mac,&cond,&loc);
90
91     ia32_decode(IA32_FULL_DECODER,(const unsigned char *)(instr->ptr()),detail);
92
93     // now find the immediate value in the locations
94     Address immediate = 0;
95
96     switch(loc.imm_size) {
97         case 8:
98             immediate = *(const unsigned long*)(instr->ptr()+loc.imm_position);
99             break;
100         case 4:
101             immediate = *(const unsigned int*)(instr->ptr()+loc.imm_position);
102             break;
103         case 2:
104             immediate = *(const unsigned short*)(instr->ptr()+loc.imm_position);
105             break;
106         case 1:
107             immediate = *(const unsigned char*)(instr->ptr()+loc.imm_position);
108             break;
109         default:
110             parsing_printf("%s[%u]:  invalid immediate size %d in insn\n",
111                 FILE__,__LINE__,loc.imm_size);
112             break;
113     }
114
115     return immediate;
116 }
117
118 // get the displacement of a relative jump or call
119
120 int get_disp(instruction *insn) {
121   return displacement(insn->ptr(), insn->type());
122 }
123
124 int count_prefixes(unsigned insnType) {
125   unsigned nPrefixes = 0;
126   if (insnType & PREFIX_OPR)
127     nPrefixes++;
128   if (insnType & PREFIX_SEG)
129     nPrefixes++;
130   if (insnType & PREFIX_OPCODE)
131     nPrefixes++;
132   if (insnType & PREFIX_REX)
133     nPrefixes++;
134   if (insnType & PREFIX_INST)
135     nPrefixes++;
136   if (insnType & PREFIX_ADDR)
137     nPrefixes++;
138   return nPrefixes;
139 }
140
141 unsigned copy_prefixes(const unsigned char *&origInsn, unsigned char *&newInsn, unsigned insnType) {
142   unsigned nPrefixes = count_prefixes(insnType);
143
144   for (unsigned u = 0; u < nPrefixes; u++)
145      *newInsn++ = *origInsn++;
146   return nPrefixes;
147 }
148
149 //Copy all prefixes but the Operand-Size and Address-Size prefixes (0x66 and 0x67)
150 unsigned copy_prefixes_nosize(const unsigned char *&origInsn, unsigned char *&newInsn, 
151                               unsigned insnType) 
152 {
153   unsigned nPrefixes = count_prefixes(insnType);
154
155   for (unsigned u = 0; u < nPrefixes; u++) {
156      if (*origInsn == 0x66 || *origInsn == 0x67)
157      {
158         origInsn++;
159         continue;
160      }
161      *newInsn++ = *origInsn++;
162   }
163   return nPrefixes;
164 }
165
166 bool convert_to_rel8(const unsigned char*&origInsn, unsigned char *&newInsn) {
167   if (*origInsn == 0x0f)
168     origInsn++;
169
170   // We think that an opcode in the 0x8? range can be mapped to an equivalent
171   // opcode in the 0x7? range...
172
173   if ((*origInsn >= 0x70) &&
174       (*origInsn < 0x80)) {
175     *newInsn++ = *origInsn++;
176     return true;
177   }
178
179   if ((*origInsn >= 0x80) &&
180       (*origInsn < 0x90)) {
181      *newInsn++ = static_cast<unsigned char>(*origInsn++ - 0x10);
182      return true;
183   }
184
185   if (*origInsn == 0xE3) {
186     *newInsn++ = *origInsn++;
187     return true;
188   }
189
190   // Oops...
191   fprintf(stderr, "Unhandled jump conversion case: opcode is 0x%x\n", *origInsn);
192   assert(0 && "Unhandled jump conversion case!");
193   return false;
194 }
195
196 bool convert_to_rel32(const unsigned char*&origInsn, unsigned char *&newInsn) {
197   if (*origInsn == 0x0f)
198     origInsn++;
199   *newInsn++ = 0x0f;
200
201   // We think that an opcode in the 0x7? range can be mapped to an equivalent
202   // opcode in the 0x8? range...
203
204   if ((*origInsn >= 0x70) &&
205       (*origInsn < 0x80)) {
206     *newInsn++ = static_cast<unsigned char>(*origInsn++ + 0x10);
207     return true;
208   }
209
210   if ((*origInsn >= 0x80) &&
211       (*origInsn < 0x90)) {
212     *newInsn++ = *origInsn++;
213     return true;
214   }
215
216   // Oops...
217   fprintf(stderr, "Unhandled jump conversion case: opcode is 0x%x\n", *origInsn);
218   assert(0 && "Unhandled jump conversion case!");
219   return false;
220 }
221
222 bool isStackFramePrecheck_gcc( const unsigned char *buffer )
223 {
224    //Currently enabled entry bytes for gaps:
225    //  0x55 - push %ebp
226    static char gap_initial_bytes[] =
227       { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
228         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
229         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
230         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
231         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
232         0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
233         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
234         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
235         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
236         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
237         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
238         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
239         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
240         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
241         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
242         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
243    return (gap_initial_bytes[*buffer] != 0);
244 }  
245
246 bool isStackFramePrecheck_msvs( const unsigned char *buffer )
247 {
248    //Currently enabled entry bytes for gaps:
249    //  0x55 - push %ebp
250    static char gap_initial_bytes[] =
251       { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
252         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
253         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
254         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
255         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
256         0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
257         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
258         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
259         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
260         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
261         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
262         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
263         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
264         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
265         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
266         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
267    return (gap_initial_bytes[*buffer] != 0);
268 }  
269
270 bool isStackFramePreamble( instruction& insn1 )
271 {       
272     instruction insn2, insn3;
273     insn2.setInstruction( insn1.ptr() + insn1.size() );       
274     insn3.setInstruction( insn2.ptr() + insn2.size() );
275
276     const unsigned char* p = insn1.op_ptr();
277     const unsigned char* q = insn2.op_ptr();
278     const unsigned char* r = insn3.op_ptr();
279     
280     unsigned Mod1_1 =  ( q[ 1 ] >> 3 ) & 0x07;
281     unsigned Mod1_2 =  q[ 1 ] & 0x07;
282     unsigned Mod2_1 =  ( r[ 1 ] >> 3 ) & 0x07;
283     unsigned Mod2_2 =  r[ 1 ] & 0x07;
284
285     if( insn1.size() != 1 )
286     {
287         return false;  //shouldn't need this, but you never know
288     }
289     
290     if( p[ 0 ] == PUSHEBP  )
291     {   
292         // Looking for mov %esp -> %ebp in one of the two
293         // following instructions.  There are two ways to encode 
294         // mov %esp -> %ebp: as '0x8b 0xec' or as '0x89 0xe5'.  
295         if( insn2.isMoveRegMemToRegMem() && 
296             ((Mod1_1 == 0x05 && Mod1_2 == 0x04) ||
297              (Mod1_1 == 0x04 && Mod1_2 == 0x05)))
298             return true;
299
300         if( insn3.isMoveRegMemToRegMem() && 
301             ((Mod2_1 == 0x05 && Mod2_2 == 0x04) ||
302              (Mod2_1 == 0x04 && Mod2_2 == 0x05)))
303             return true;
304     }
305     
306     return false;
307 }
308
309 // We keep an array-let that represents various fixed
310 // insns
311 unsigned char illegalRep[2] = {0x0f, 0x0b};
312 unsigned char trapRep[1] = {0xCC};
313
314 instruction *instruction::copy() const {
315     // Or should we copy? I guess it depends on who allocated
316     // the memory...
317     return new instruction(*this);
318 }
319
320 void instruction::generateIllegal(codeGen &gen) {
321     instruction insn;
322     insn.setInstruction(illegalRep);
323     insn.generate(gen);
324 }
325
326 void instruction::generateTrap(codeGen &gen) {
327     instruction insn;
328     insn.setInstruction(trapRep);
329     insn.generate(gen);
330 }
331
332 /*
333  * change the insn at addr to be a branch to newAddr.
334  *   Used to add multiple tramps to a point.
335  */
336
337 void instruction::generateBranch(codeGen &gen,
338                                  Address fromAddr, Address toAddr)
339 {
340   GET_PTR(insn, gen);
341   long disp;
342
343   disp = toAddr - (fromAddr + 2);
344   if (is_disp8(disp)) {
345      *insn++ = 0xEB;
346      *((signed char*) insn) = (signed char) disp;
347      insn += sizeof(signed char);
348      SET_PTR(insn, gen);
349      return;
350   }
351   /*  
352   disp = toAddr - (fromAddr + 4);
353   if (is_disp16(disp) && gen.addrSpace()->getAddressWidth() != 8) {
354      *insn++ = 0x66;
355      *insn++ = 0xE9;
356      *((signed short*) insn) = (signed short) disp;
357      insn += sizeof(signed short);
358      SET_PTR(insn, gen);
359      return;
360   }
361   */
362   disp = toAddr - (fromAddr + 5);
363   if (is_disp32(disp) || gen.addrSpace()->getAddressWidth() == 4) {
364      generateBranch(gen, disp);
365      return;
366   }
367   
368   if(gen.addrSpace()->getAddressWidth() == 8)
369   {
370       generateBranch64(gen, toAddr);
371   }
372   else
373   {
374       generateBranch32(gen, toAddr);
375   }
376   return;
377 }
378
379 void instruction::generateBranch(codeGen &gen,
380                                  int disp32)
381 {
382    if (disp32 >= 0)
383       assert ((unsigned)disp32 < unsigned(1<<31));
384    else
385       assert ((unsigned)(-disp32) < unsigned(1<<31));
386    GET_PTR(insn, gen);
387    *insn++ = 0xE9;
388    *((int *)insn) = disp32;
389    insn += sizeof(int);
390   
391    SET_PTR(insn, gen);
392    return;
393 }
394
395
396 // Unified the 64-bit push between branch and call
397 void instruction::generatePush64(codeGen &gen, Address val)
398 {
399   GET_PTR(insn, gen);
400   for (int i = 3; i >= 0; i--) {
401     short word = static_cast<unsigned char>((val >> (16 * i)) & 0xffff);
402     *insn++ = 0x66; // operand size override
403     *insn++ = 0x68; // push immediate (16-bits b/c of prefix)
404     *(short *)insn = word;
405     insn += 2;
406   }
407   SET_PTR(insn, gen);
408 }
409
410 void instruction::generateBranch64(codeGen &gen, Address to)
411 {
412     // "long jump" - generates sequence to jump to any 64-bit address
413     // pushes the value on the stack (using 4 16-bit pushes) the uses a 'RET'
414
415   generatePush64(gen, to);
416
417   GET_PTR(insn, gen);
418   *insn++ = 0xC3; // RET
419   SET_PTR(insn, gen);
420
421 }
422
423 void instruction::generateBranch32(codeGen &gen, Address to)
424 {
425    // "long jump" - generates sequence to jump to any 32-bit address
426    emitPushImm(to, gen);
427    
428    GET_PTR(insn, gen);
429    *insn++ = 0xC3; // RET
430    SET_PTR(insn, gen);
431 }
432
433 void instruction::generateCall(codeGen &gen,
434                                Address from,
435                                Address target)
436 {
437   //assert(target);
438   long disp = target - (from + CALL_REL32_SZ);
439   
440   if (is_disp32(disp)) {
441     GET_PTR(insn, gen);
442     *insn++ = 0xE8;
443     *((int *)insn) = (int) disp;
444     insn += sizeof(int);
445     SET_PTR(insn, gen);
446   }
447   else {
448     // Wheee....
449     // We use a technique similar to our 64-bit
450     // branch; push the return addr onto the stack (from),
451     // then push to, then return. 
452     
453     // This looks like
454     // A: push D
455     // B: push <...>
456     // C: return
457     // D:
458
459 #if defined(arch_x86_64)
460     // So we need to know where D is off of "from"
461     if(gen.addrSpace()->getAddressWidth() == 8)
462     {
463         generatePush64(gen, from+CALL_ABS64_SZ);
464         generateBranch64(gen, target);
465     }
466     else
467     {
468         emitPushImm(from+CALL_ABS32_SZ, gen);
469         generateBranch32( gen, target);
470     }
471 #else
472     emitPushImm(from+CALL_ABS32_SZ, gen);
473     generateBranch32( gen, target);
474 #endif
475   }
476 }
477
478 void instruction::generateNOOP(codeGen &gen, unsigned size) {
479     // Be more efficient here...
480     while (size) {
481         GET_PTR(insn, gen);
482         *insn++ = NOP;
483         SET_PTR(insn, gen);
484         size -= sizeof(unsigned char);
485     }
486 }
487
488 void instruction::generate(codeGen &gen) {
489     assert(ptr_);
490     assert(size_);
491     memcpy(gen.cur_ptr(), ptr_, size_);
492     gen.moveIndex(size_);
493 }
494
495 unsigned instruction::spaceToRelocate() const {
496     // List of instructions that might be painful:
497     // jumps (displacement will change)
498     // call (displacement will change)
499     // PC-relative ops
500
501     // TODO: pc-relative ops
502
503     // longJumpSize == size of code needed to get
504     // anywhere in memory space.
505 #if defined(arch_x86_64)
506     const int longJumpSize = JUMP_ABS64_SZ;
507 #else
508     const int longJumpSize = JUMP_ABS32_SZ;
509 #endif
510
511
512     // Assumption: rewriting calls into immediates will
513     // not be larger than rewriting a call into a call...
514
515     if (!((type() & REL_B) ||
516           (type() & REL_W) ||
517           (type() & REL_D) ||
518           (type() & REL_D_DATA))) {
519       return size();
520     }
521     
522     // Now that the easy case is out of the way...
523     
524     if (type() & IS_JUMP) {
525       // Worst-case: prefixes + max-displacement branch
526       return count_prefixes(type()) + longJumpSize;
527     }
528     if (type() & IS_JCC) {
529       // Jump conditional; jump past jump; long jump
530       return count_prefixes(type()) + 2 + 2 + longJumpSize;
531     }
532     if (type() & IS_CALL) {
533       // Worst case is approximated by two long jumps (AMD64) or a REL32 (x86)
534       unsigned size;
535 #if defined(arch_x86_64)
536       size = 2*JUMP_ABS64_SZ+count_prefixes(type());
537 #else
538       size = JUMP_SZ+count_prefixes(type());
539 #endif
540       size = (size > CALL_RELOC_THUNK) ? size : CALL_RELOC_THUNK;
541       return size;
542     }
543 #if defined(arch_x86_64)
544     if (type() & REL_D_DATA) {
545       // Worst-case: replace RIP with push of IP, use, and cleanup
546       // 8: unknown; previous constant
547       return count_prefixes(type()) + size() + 8;
548     }
549 #endif
550
551     assert(0);
552     return 0;
553 }
554
555 /*
556 static void addPatch(codeGen &gen, patchTarget *src, imm_location_t &imm)
557 {
558    switch (imm.size) {
559       case 1:
560          relocPatch::patch_type_t ptype = imm.is_relative ? relocPatch::pcrel :
561             relocPatch::abs;
562          Dyninst::Offset off = imm.is_relative ? gen.getIndex() : 0;
563          gen.addPatch(imm.words[i], src, imm.size, ptype, off);
564          break;
565       case 2:
566          gen.addPatch(imm.words[0], src, imm.size, reloc_patch::abs_quad1);
567          gen.addPatch(imm.words[1], src, imm.size, reloc_patch::abs_quad2);
568          break;
569       case 4:
570          gen.addPatch(imm.words[0], src, imm.size, reloc_patch::abs_quad1);
571          gen.addPatch(imm.words[1], src, imm.size, reloc_patch::abs_quad2);
572          gen.addPatch(imm.words[2], src, imm.size, reloc_patch::abs_quad3);
573          gen.addPatch(imm.words[3], src, imm.size, reloc_patch::abs_quad4);
574          break;
575       default:
576          assert(0);
577    }
578 }
579 */
580
581 class pcRelJump : public pcRelRegion {
582 private:
583    Address addr_targ;
584    patchTarget *targ;
585     bool copy_prefixes_;
586
587    Address get_target();
588 public:
589    pcRelJump(patchTarget *t, const instruction &i, bool copyPrefixes = true);
590    pcRelJump(Address target, const instruction &i, bool copyPrefixes = true);
591    virtual unsigned apply(Address addr);
592    virtual unsigned maxSize();        
593    virtual bool canPreApply();
594    virtual ~pcRelJump();
595 };
596
597 pcRelJump::pcRelJump(patchTarget *t, const instruction &i, bool copyPrefixes) :
598    pcRelRegion(i),
599    addr_targ(0x0),
600    targ(t),
601    copy_prefixes_(copyPrefixes)
602 {
603 }
604
605 pcRelJump::pcRelJump(Address target, const instruction &i, bool copyPrefixes) :
606    pcRelRegion(i),
607    addr_targ(target),
608    targ(NULL),
609    copy_prefixes_(copyPrefixes)
610 {
611 }
612
613 Address pcRelJump::get_target() 
614 {
615    if (targ)
616       return targ->get_address();
617    return addr_targ;
618 }
619
620 pcRelJump::~pcRelJump()
621 {
622 }
623
624 unsigned pcRelJump::apply(Address addr)
625 {
626    const unsigned char *origInsn = orig_instruc.ptr();
627    unsigned insnType = orig_instruc.type();
628    unsigned char *orig_loc;
629         
630    GET_PTR(newInsn, *gen);
631    orig_loc = newInsn;
632     if (copy_prefixes_) {
633    copy_prefixes(origInsn, newInsn, insnType);
634     }
635    SET_PTR(newInsn, *gen);
636     
637    instruction::generateBranch(*gen, addr, get_target());
638    REGET_PTR(newInsn, *gen);
639    return (unsigned) (newInsn - orig_loc);
640 }
641
642 unsigned pcRelJump::maxSize()
643 {
644    unsigned prefixes = count_prefixes(orig_instruc.type());
645 #if defined(arch_x86_64)
646    if (gen->addrSpace()->getAddressWidth() == 8)
647       return prefixes + JUMP_ABS64_SZ;
648 #endif
649    return prefixes + JUMP_SZ;
650 }
651
652 bool pcRelJump::canPreApply()
653 {
654    return gen->startAddr() && (!targ || get_target());
655 }
656
657 class pcRelJCC : public pcRelRegion {
658 private:
659    Address addr_targ;
660    patchTarget *targ;
661
662    Address get_target();
663 public:
664    pcRelJCC(patchTarget *t, const instruction &i);
665    pcRelJCC(Address target, const instruction &i);
666    virtual unsigned apply(Address addr);
667    virtual unsigned maxSize();        
668    virtual bool canPreApply();
669    virtual ~pcRelJCC();
670 };
671
672 pcRelJCC::pcRelJCC(patchTarget *t, const instruction &i) :
673    pcRelRegion(i),
674    addr_targ(0x0),
675    targ(t)
676 {
677 }
678
679 pcRelJCC::pcRelJCC(Address target, const instruction &i) :
680    pcRelRegion(i),
681    addr_targ(target),
682    targ(NULL)
683 {
684 }
685
686 Address pcRelJCC::get_target() 
687 {
688    if (targ)
689       return targ->get_address();
690    return addr_targ;
691 }
692
693 pcRelJCC::~pcRelJCC()
694 {
695 }
696
697 unsigned pcRelJCC::apply(Address addr)
698 {
699    const unsigned char *origInsn = orig_instruc.ptr();
700    unsigned insnType = orig_instruc.type();
701    unsigned char *orig_loc;
702    Address target = get_target();
703    Address potential;
704    signed long disp;
705    GET_PTR(newInsn, *gen);
706    orig_loc = newInsn;
707
708    copy_prefixes_nosize(origInsn, newInsn, insnType); 
709    
710    //8-bit jump
711    potential = addr + 2;
712    disp = target - potential;
713    if (is_disp8(disp)) {
714       convert_to_rel8(origInsn, newInsn);
715       *newInsn++ = (signed char) disp;
716       SET_PTR(newInsn, *gen);
717       return (unsigned) (newInsn - orig_loc);
718    }
719
720    //Can't convert E3 jumps to more than 8-bits
721    if (*origInsn != 0xE3) {
722      /*
723       //16-bit jump
724       potential = addr + 5;
725       disp = target - potential;
726       if (is_disp16(disp) && gen->addrSpace()->getAddressWidth() != 8) {
727          *newInsn++ = 0x66; //Prefix to shift 32-bit to 16-bit
728          convert_to_rel32(origInsn, newInsn);
729          *((signed short *) newInsn) = (signed short) disp;
730          newInsn += 2;
731          SET_PTR(newInsn, *gen);
732          return (unsigned) (newInsn - orig_loc);
733       }
734      */
735       //32-bit jump
736       potential = addr + 6;
737       disp = target - potential;
738       if (is_disp32(disp)) {
739          convert_to_rel32(origInsn, newInsn);
740          *((signed int *) newInsn) = (signed int) disp;
741          newInsn += 4;
742          SET_PTR(newInsn, *gen);
743          return (unsigned) (newInsn - orig_loc);
744       }
745    }
746    
747    // We use a three-step branch system that looks like so:
748    //   jump conditional <A> 
749    // becomes
750    //   jump conditional <B>
751    //   jump <C>
752    //   B: jump <A>
753    //   C: ... next insn
754
755    // Moves as appropriate...
756    convert_to_rel8(origInsn, newInsn);
757    // We now want a 2-byte branch past the branch at B
758    *newInsn++ = 2;
759    
760    // Now for the branch at B- <jumpSize> unconditional branch
761    *newInsn++ = 0xEB; 
762    unsigned char *fill_in_jumpsize = newInsn++;
763    //*newInsn++ = (char) jumpSize(newDisp);
764    
765    // And the branch at C
766    SET_PTR(newInsn, *gen);
767    // Original address is a little skewed... 
768    // We've moved past the original address (to the tune of nPrefixes + 2 (JCC) + 2 (J))
769    Address currAddr = addr + (unsigned) (newInsn - orig_loc);
770    instruction::generateBranch(*gen, currAddr, target);
771    REGET_PTR(newInsn, *gen);
772
773    //Go back and fill in the size of the jump at B into the 'jump <C>'
774    signed char tmp = (signed char) (newInsn - fill_in_jumpsize) - 1;
775    *fill_in_jumpsize = tmp;
776
777    return (unsigned) (newInsn - orig_loc);
778 }
779
780 unsigned pcRelJCC::maxSize()
781 {
782    unsigned prefixes = count_prefixes(orig_instruc.type());
783 #if defined(arch_x86_64)
784    if (gen->addrSpace()->getAddressWidth() == 8)
785       return prefixes + JUMP_ABS64_SZ + 4;
786 #endif
787    return prefixes + JUMP_REL32_SZ;
788 }
789
790 bool pcRelJCC::canPreApply()
791 {
792    return gen->startAddr() && (!targ || get_target());
793 }
794
795 class pcRelCall: public pcRelRegion {
796 private:
797    Address targ_addr;
798    patchTarget *targ;
799
800    Address get_target();
801 public:
802    pcRelCall(patchTarget *t, const instruction &i);
803    pcRelCall(Address targ_addr, const instruction &i);
804
805    virtual unsigned apply(Address addr);
806    virtual unsigned maxSize();        
807    virtual bool canPreApply();
808    ~pcRelCall();
809 };
810
811 pcRelCall::pcRelCall(patchTarget *t, const instruction &i) :
812    pcRelRegion(i),
813    targ_addr(0x0),
814    targ(t)
815 {
816 }
817
818 pcRelCall::pcRelCall(Address target, const instruction &i) :
819    pcRelRegion(i),
820    targ_addr(target),
821    targ(NULL)
822 {
823 }
824
825 Address pcRelCall::get_target()
826 {
827    if (targ)
828       return targ->get_address();
829    return targ_addr;
830 }
831
832 pcRelCall::~pcRelCall()
833 {
834 }
835
836 unsigned pcRelCall::apply(Address addr)
837 {
838    const unsigned char *origInsn = orig_instruc.ptr();
839    unsigned insnType = orig_instruc.type();
840    unsigned char *orig_loc;
841    GET_PTR(newInsn, *gen);
842    orig_loc = newInsn;
843
844    copy_prefixes_nosize(origInsn, newInsn, insnType);
845    SET_PTR(newInsn, *gen);
846    instruction::generateCall(*gen, addr, get_target());
847    REGET_PTR(newInsn, *gen);
848    return (unsigned) (newInsn - orig_loc);
849 }
850
851 unsigned pcRelCall::maxSize()
852 {
853    unsigned prefixes = count_prefixes(orig_instruc.type());
854 #if defined(arch_x86_64)
855    if (gen->addrSpace()->getAddressWidth() == 8)
856       return prefixes + 2*JUMP_ABS64_SZ;
857 #endif
858    return prefixes + JUMP_REL32_SZ;
859 }
860
861 bool pcRelCall::canPreApply()
862 {
863    return gen->startAddr() && (!targ || get_target());
864 }
865
866 class pcRelData : public pcRelRegion {
867 private:
868    Address data_addr;
869 public:
870    pcRelData(Address a, const instruction &i);
871    virtual unsigned apply(Address addr);
872    virtual unsigned maxSize();        
873    virtual bool canPreApply();
874 };
875
876 pcRelData::pcRelData(Address a, const instruction &i) :
877    pcRelRegion(i),
878    data_addr(a)
879 {
880 }
881
882 #define REL_DATA_MAXSIZE 2/*push r*/ + 10/*movImmToReg64*/ + 7/*orig insn*/ + 2/*pop r*/
883
884 #if !defined(arch_x86_64)
885 unsigned pcRelData::apply(Address) {
886    assert(0);
887    return 0;
888 }
889
890 #else
891 unsigned pcRelData::apply(Address addr) 
892 {
893    // We may need to change these from 32-bit relative
894    // to 64-bit absolute. This happens with the jumps and calls
895    // as well, but it's better encapsulated there.
896    
897    // We have three options:
898    // a) 32-bit relative (AKA "original").
899    // b) 32-bit absolute version (where 32-bit relative would fail but we're low)
900    // c) 64-bit absolute version
901    const unsigned char *origInsn = orig_instruc.ptr();
902    unsigned insnType = orig_instruc.type();
903    unsigned insnSz = orig_instruc.size();   
904    bool is_data_abs64 = false;
905    unsigned nPrefixes = count_prefixes(insnType);
906    signed long newDisp = data_addr - addr;
907    unsigned char *orig_loc;
908    GET_PTR(newInsn, *gen);
909    orig_loc = newInsn;
910
911    // count opcode bytes (1 or 2)
912    unsigned nOpcodeBytes = 1;
913    if (*(origInsn + nPrefixes) == 0x0F)
914       nOpcodeBytes = 2;
915    
916    Register pointer_reg = (Register)-1;
917      
918    if (!is_disp32(newDisp+insnSz) && !is_addr32(data_addr)) {
919       // Case C: replace with 64-bit.
920       is_data_abs64 = true;
921       unsigned char mod_rm = *(origInsn + nPrefixes + nOpcodeBytes);
922       pointer_reg = (mod_rm & 0x38) != 0 ? 0 : 3;
923       SET_PTR(newInsn, *gen);
924       emitPushReg64(pointer_reg, *gen);
925       emitMovImmToReg64(pointer_reg, data_addr, true, *gen);
926       REGET_PTR(newInsn, *gen);
927    }
928
929    const unsigned char* origInsnStart = origInsn;
930
931    // In other cases, we can rewrite the insn directly; in the 64-bit case, we
932    // still need to copy the insn
933    copy_prefixes(origInsn, newInsn, insnType);
934
935    if (*origInsn == 0x0F) {
936       *newInsn++ = *origInsn++;
937    }
938      
939    // And the normal opcode
940    *newInsn++ = *origInsn++;
941    
942    if (is_data_abs64) {
943       // change ModRM byte to use [pointer_reg]: requires
944       // us to change last three bits (the r/m field)
945       // to the value of pointer_reg
946       unsigned char mod_rm = *origInsn++;
947       assert(pointer_reg != (Register)-1);
948       mod_rm = (mod_rm & 0xf8) + pointer_reg;
949       *newInsn++ = mod_rm;
950    }
951    else if (is_disp32(newDisp+insnSz)) {
952       // Whee easy case
953       *newInsn++ = *origInsn++;
954       // Size doesn't change....
955       *((int *)newInsn) = (int)(newDisp - insnSz);
956       newInsn += 4;
957    }
958    else if (is_addr32(data_addr)) {
959       assert(!is_disp32(newDisp+insnSz));
960       unsigned char mod_rm = *origInsn++;
961       
962       // change ModRM byte to use SIB addressing (r/m == 4)
963       mod_rm = (mod_rm & 0xf8) + 4;
964       *newInsn++ = mod_rm;
965       
966       // SIB == 0x25 specifies [disp32] addressing when mod == 0
967       *newInsn++ = 0x25;
968       
969       // now throw in the displacement (the absolute 32-bit address)
970       *((int *)newInsn) = (int)(data_addr);
971       newInsn += 4;
972    }
973    else {
974       // Should never be reached...
975       assert(0);
976    }
977    
978    // there may be an immediate after the displacement for RIP-relative
979    // so we copy over the rest of the instruction here
980    origInsn += 4;
981    while (origInsn - origInsnStart < (int)insnSz)
982       *newInsn++ = *origInsn++;
983    
984    SET_PTR(newInsn, *gen);
985    
986    if (is_data_abs64) {
987       // Cleanup on aisle pointer_reg...
988       assert(pointer_reg != (Register)-1);
989       emitPopReg64(pointer_reg, *gen);
990    }
991    return (unsigned) (newInsn - orig_loc);
992 }
993 #endif
994
995 unsigned pcRelData::maxSize() 
996 {
997    unsigned prefixes = count_prefixes(orig_instruc.type());
998    return REL_DATA_MAXSIZE + prefixes;
999 }
1000
1001 bool pcRelData::canPreApply()
1002 {
1003    return (gen->startAddr() != 0x0);
1004 }
1005
1006 bool instruction::generate(codeGen &gen,
1007                            AddressSpace *addrSpace,
1008                            Address origAddr, // Could be kept in the instruction class.
1009                            Address newAddr,
1010                            patchTarget *fallthroughOverride,
1011                            patchTarget *targetOverride) 
1012 {
1013    // We grab the maximum space we might need
1014    GET_PTR(insnBuf, gen);
1015
1016    /* 
1017       Relative address instructions need to be modified. The relative address
1018       can be a 8, 16, or 32-byte displacement relative to the next instruction.
1019       Since we are relocating the instruction to a different area, we have
1020       to replace 8 and 16-byte displacements with 32-byte displacements.
1021        
1022       All relative address instructions are one or two-byte opcode followed
1023       by a displacement relative to the next instruction:
1024        
1025       CALL rel16 / CALL rel32
1026       Jcc rel8 / Jcc rel16 / Jcc rel32
1027       JMP rel8 / JMP rel16 / JMP rel32
1028        
1029       The only two-byte opcode instructions are the Jcc rel16/rel32,
1030       all others have one byte opcode.
1031        
1032       The instruction JCXZ/JECXZ rel8 does not have an equivalent with rel32
1033       displacement. We must generate code to emulate this instruction:
1034        
1035       JCXZ rel8
1036        
1037       becomes
1038        
1039       A0: JCXZ 2 (jump to A4)
1040       A2: JMP 5  (jump to A9)
1041       A4: JMP rel32 (relocated displacement)
1042       A9: ...
1043        
1044    */
1045
1046    const unsigned char *origInsn = ptr();
1047    unsigned insnType = type();
1048    unsigned insnSz = size();
1049    // This moves as we emit code
1050    unsigned char *newInsn = insnBuf;
1051
1052    // Check to see if we're doing the "get my PC" via a call
1053    // We do this first as those aren't "real" jumps.
1054    if (isCall() && !isCallIndir()) {
1055       // A possibility...
1056       // Two types: call(0) (AKA call(me+5));
1057       // or call to a move/return combo.
1058
1059       // First, call(me)
1060       Address target = getTarget(origAddr);
1061       // Big if tree: "if we go to the next insn"
1062       // Also could do with an instrucIter... or even have
1063       // parsing label it for us. 
1064       // TODO: label in parsing (once)
1065         
1066       if (target == (origAddr + size())) {
1067          if(addrSpace->proc())
1068          {
1069             *newInsn = 0x68; // Push; we're replacing "call 0" with "push original IP"
1070             newInsn++;    
1071             Address EIP = origAddr + size();
1072             unsigned int *temp = (unsigned int *) newInsn;
1073             *temp = EIP;
1074             // No 9-byte jumps...
1075             assert(sizeof(unsigned int) == 4); // should be a compile-time assert
1076             newInsn += sizeof(unsigned int);
1077             assert((newInsn - insnBuf) == 5);
1078             SET_PTR(newInsn, gen);
1079             goto done;
1080          }
1081          else
1082          {
1083             *newInsn = 0xE8;
1084             newInsn++;
1085             unsigned int *temp = (uint32_t *) newInsn;
1086             *temp = 0;
1087             newInsn += sizeof(uint32_t);
1088             Address offset = origAddr - newAddr;
1089             *newInsn = 0x81;
1090             newInsn++;
1091             *newInsn = 0x04;
1092             newInsn++;
1093             *newInsn = 0x24;
1094             newInsn++;
1095             temp =  (uint32_t *) newInsn;
1096             *temp = offset;
1097             newInsn += sizeof(uint32_t);          
1098             assert((newInsn - insnBuf) == 12);
1099             SET_PTR(newInsn, gen);
1100             goto done;    
1101          }      
1102       }
1103       else if (addrSpace->isValidAddress(target)) {
1104          // Get us an instrucIter
1105           const unsigned char* buf = reinterpret_cast<const unsigned char*>(addrSpace->getPtrToInstruction(target));
1106           InstructionDecoder d(buf, 32);
1107           d.setMode(addrSpace->getAddressWidth() == 8);
1108           Instruction::Ptr firstInsn = d.decode();
1109           Instruction::Ptr secondInsn = d.decode();
1110           if(firstInsn && firstInsn->getOperation().getID() == e_mov
1111              && firstInsn->readsMemory() && !firstInsn->writesMemory()
1112              && secondInsn && secondInsn->getCategory() == c_ReturnInsn)
1113           {
1114               // We need to fake this by figuring out the register
1115             // target (assuming we're moving stack->reg),
1116             // and constructing an immediate with the value of the
1117             // original address of the call (+size)
1118             // This was copied from function relocation code... I 
1119             // don't understand most of it -- bernat
1120               const unsigned char *ptr = (const unsigned char*)(firstInsn->ptr());
1121             unsigned char modrm = *(ptr + 1);
1122             unsigned char reg = static_cast<unsigned char>((modrm >> 3) & 0x3);
1123             // Source register... 
1124             if ((modrm == 0x0c) || (modrm == 0x1c)) {
1125                // Check source register (%esp == 0x24)
1126                if ((*(ptr + 2) == 0x24)) {
1127                  if(addrSpace->proc())
1128                  {
1129                    // Okay, put the PC into the 'reg'
1130                    Address EIP = origAddr + size();
1131                    *newInsn = static_cast<unsigned char>(0xb8 + reg); // MOV family, destination of the register encoded by
1132                    // 'reg', source is an Iv immediate
1133                    newInsn++;
1134                    unsigned int *temp = (unsigned int *)newInsn;
1135                    *temp = EIP;
1136                    //assert(sizeof(unsigned int *)==4);
1137                    //newInsn += sizeof(unsigned int *);
1138                    newInsn += 4;  // fix for AMD64
1139                    SET_PTR(newInsn, gen);
1140                    goto done;
1141                  }
1142                  else
1143                  {
1144                    *newInsn = 0xE8;
1145                    newInsn++;
1146                    unsigned int *temp = (uint32_t *) newInsn;
1147                    *temp = 0;
1148                    newInsn += sizeof(unsigned int);
1149                    Address offset = origAddr - newAddr;
1150                    *newInsn = 0x81;
1151                    newInsn++;
1152                    *newInsn = 0x04;
1153                    newInsn++;
1154                    *newInsn = 0x24;
1155                    newInsn++;
1156                    temp =  (uint32_t*) newInsn;
1157                    *temp = offset;
1158                    newInsn += sizeof(uint32_t);   
1159                    *newInsn = static_cast<unsigned char>(0x58 + reg); // POP family
1160                    newInsn++;
1161                    SET_PTR(newInsn, gen);
1162                    goto done;
1163                  }
1164                  
1165                }
1166             }
1167          }
1168       }
1169       else {
1170          fprintf(stderr, "Warning: call at 0x%lx did not have a valid "
1171                  "calculated target addr 0x%lx\n", origAddr, target);
1172       }
1173    }
1174
1175    if (!((insnType & REL_B) ||
1176          (insnType & REL_W) ||
1177          (insnType & REL_D) ||
1178          (insnType & REL_D_DATA))) {
1179      // Normal insn, not addr relative
1180      for (unsigned u = 0; u < insnSz; u++)
1181        *newInsn++ = *origInsn++;
1182      SET_PTR(newInsn, gen);
1183      goto done;
1184    }
1185
1186    // We're addr-relative...
1187    Address orig_target;
1188    if (dynamic_cast<toAddressPatch *>(targetOverride)) {
1189       //targetOverride's address is known now, we'll keep the address around
1190       // rather than the targetOverride.
1191       orig_target = targetOverride->get_address();
1192       targetOverride = NULL;
1193    }
1194    else {
1195       orig_target = origAddr + size() + get_disp(this);
1196    }
1197    
1198 #if defined(arch_x86_64)
1199    if (insnType & REL_D_DATA) {
1200       // Create pcRelRegion that eventually will call pcRelData::apply
1201       pcRelData *pcr_data = new pcRelData(orig_target, *this);
1202       assert(pcr_data);
1203       gen.addPCRelRegion(pcr_data);
1204       goto done;
1205    }
1206 #endif
1207    
1208    if (insnType & IS_JUMP) {
1209      // Create pcRelRegion that eventually will call pcRelJump::apply
1210      pcRelJump *pcr_jump;
1211      if (targetOverride) {
1212         pcr_jump = new pcRelJump(targetOverride, *this);
1213      }
1214      else {
1215         pcr_jump = new pcRelJump(orig_target, *this);
1216      }
1217      assert(pcr_jump);
1218      gen.addPCRelRegion(pcr_jump);
1219      goto done;
1220    }
1221
1222    if (insnType & IS_JCC) {
1223      // Create pcRelRegion that eventually will call pcRelJCC::apply
1224      pcRelJCC *pcr_jcc;
1225      if (targetOverride) {
1226         pcr_jcc = new pcRelJCC(targetOverride, *this);
1227      }
1228      else {
1229         pcr_jcc = new pcRelJCC(orig_target, *this);
1230      }
1231      assert(pcr_jcc);
1232      gen.addPCRelRegion(pcr_jcc);
1233      goto done;
1234    }
1235
1236    if (insnType & IS_CALL) {
1237      // Create pcRelRegion that eventually will call pcRelCall::apply
1238      pcRelCall *pcr_call;
1239      if (targetOverride) {
1240         pcr_call = new pcRelCall(targetOverride, *this);
1241      }
1242      else {
1243         pcr_call = new pcRelCall(orig_target, *this);
1244      }
1245      assert(pcr_call);
1246      gen.addPCRelRegion(pcr_call);
1247      goto done;
1248    }
1249
1250    //If we get here, then we either didn't handle a case of PC-relative instructions,
1251    // or we mis-identified an instruction as PC-relative.
1252    assert(0);
1253    return false;
1254
1255  done:
1256    if (fallthroughOverride) {
1257        pcRelJump *ft_jump = new pcRelJump(fallthroughOverride, *this, false);
1258        assert(ft_jump);
1259        gen.addPCRelRegion(ft_jump);
1260    }
1261
1262    return true;
1263 }
1264
1265 #if defined(arch_x86_64)
1266 unsigned instruction::jumpSize(long disp, unsigned addr_width) 
1267 {
1268    if (addr_width == 8 && !is_disp32(disp))
1269       return JUMP_ABS64_SZ;
1270    return JUMP_SZ;
1271 }
1272 #else
1273 unsigned instruction::jumpSize(long /*disp*/, unsigned /*addr_width*/) 
1274 {
1275    return JUMP_SZ;
1276 }
1277 #endif
1278
1279 unsigned instruction::jumpSize(Address from, Address to, unsigned addr_width) 
1280 {
1281     long disp = to - (from + JUMP_SZ);
1282     return jumpSize(disp, addr_width);
1283 }
1284
1285 #if defined(arch_x86_64)
1286 unsigned instruction::maxJumpSize(unsigned addr_width) 
1287 {
1288    if (addr_width == 8)
1289       return JUMP_ABS64_SZ;
1290    return JUMP_SZ;
1291 }
1292 #else
1293 unsigned instruction::maxJumpSize(unsigned /*addr_width*/) 
1294 {
1295    return JUMP_SZ;
1296 }
1297 #endif
1298
1299 bool instruction::isCmp() const {
1300     if(*op_ptr_ == CMP_EB_GB || *op_ptr_ == CMP_EV_GV ||
1301        *op_ptr_ == CMP_GB_EB || *op_ptr_ == CMP_GV_EV ||
1302        *op_ptr_ == CMP_AL_LB || *op_ptr_ == CMP_RAX_LZ)
1303     {
1304         return true;
1305     }
1306
1307     if(*op_ptr_ == 0x80 || *op_ptr_ == 0x81 || *op_ptr_ == 0x83) 
1308     {
1309         // group 1 opcodes -- operation depends on reg (bits 3-5) of
1310         // modr/m byte
1311         const unsigned char *p = op_ptr_+1;
1312         if( (*p & (7<<3)) == (7<<3))
1313             return true;
1314     }
1315
1316     return false;
1317 }
1318
1319 #define SIB_SET_REG(x, y) ((x) |= ((y) & 7))
1320 #define SIB_SET_INDEX(x, y) ((x) |= (((y) & 7) << 3))
1321 #define SIB_SET_SS(x, y) ((x) | (((y) & 3) << 6))
1322
1323 typedef struct parsed_instr_t {
1324    int num_prefixes;
1325    int opcode_size;
1326    int disp_position;
1327    int disp_size;
1328    int imm_position;
1329    int imm_size;
1330
1331    unsigned char sib_byte;
1332    unsigned char modrm_byte;
1333    int sib_position; 
1334    int modrm_position;
1335
1336    int address_size;
1337    int modrm_operand;
1338
1339    int rex_position;
1340    int rex_byte;
1341    int rex_w;
1342    int rex_r;
1343    int rex_x;
1344    int rex_b;
1345
1346    ia32_instruction orig_instr;
1347    ia32_entry *entry;
1348 } parse_instr_t;
1349
1350 bool instruction::getUsedRegs(pdvector<int> &regs) {
1351    const unsigned char *insn_ptr = ptr();
1352
1353    struct ia32_memacc memacc[3];
1354    struct ia32_condition cond;
1355    struct ia32_locations loc;
1356    ia32_entry *entry;
1357    ia32_instruction orig_instr(memacc, &cond, &loc);
1358    ia32_decode(IA32_DECODE_MEMACCESS | IA32_DECODE_CONDITION,
1359                insn_ptr, orig_instr);
1360    entry = orig_instr.getEntry();
1361
1362    if (orig_instr.getPrefix()->getPrefix(1) != 0)
1363       //The instruction accesses memory via segment registers.  Disallow.
1364       return false;
1365    
1366    if (loc.modrm_position == -1)
1367       //Only supporting MOD/RM instructions now
1368       return false; 
1369
1370    if (loc.address_size == 1)
1371       //Don't support 16-bit instructions yet
1372       return false;
1373
1374    if (loc.modrm_reg == 4 && !loc.rex_r)
1375       //The non-memory access register is %rsp/%esp, we can't work with
1376       // this register due to our register saving techniques.
1377       return false;
1378
1379    if (loc.modrm_mod == 3)
1380       //This instruction doesn't use the MOD/RM to access memory
1381       return false;
1382
1383    for (unsigned i=0; i<3; i++) {
1384       const ia32_operand& op = entry->operands[i];
1385       if (op.admet == am_O) {
1386          //The MOD/RM specifies a register that's used
1387          int regused = loc.modrm_reg;
1388          if (loc.address_size == 4) {
1389             regused |= loc.rex_r << 4;
1390          }
1391          regs.push_back(regused);
1392       }
1393       else if (op.admet == am_reg) {
1394         using namespace Dyninst::InstructionAPI;
1395          //The instruction implicitely references a memory instruction
1396          switch (op.optype) {
1397             case r_AH:   
1398             case r_AL:   
1399             case r_eAX:
1400             case r_EAX:
1401                regs.push_back(REGNUM_RAX);
1402                if (loc.rex_byte) regs.push_back(REGNUM_R8);
1403                break;
1404             case r_BH:
1405             case r_BL:
1406             case r_eBX:
1407             case r_EBX:
1408                regs.push_back(REGNUM_RBX);
1409                if (loc.rex_byte) regs.push_back(REGNUM_R11);
1410                break;
1411             case r_CH:   
1412             case r_CL:   
1413             case r_eCX:
1414             case r_ECX:
1415                regs.push_back(REGNUM_RCX);
1416                if (loc.rex_byte) regs.push_back(REGNUM_R9);
1417                break;
1418             case r_DL:
1419             case r_DH:
1420             case r_eDX:
1421             case r_EDX:
1422                regs.push_back(REGNUM_RDX);
1423                if (loc.rex_byte) regs.push_back(REGNUM_R10);
1424                break;
1425             case r_eSP:
1426             case r_ESP:
1427                regs.push_back(REGNUM_RSP);
1428                if (loc.rex_byte) regs.push_back(REGNUM_R12);
1429                break;
1430             case r_eBP:
1431             case r_EBP:
1432                regs.push_back(REGNUM_RBP);
1433                if (loc.rex_byte) regs.push_back(REGNUM_R13);
1434                break;
1435             case r_eSI:
1436             case r_ESI:
1437                regs.push_back(REGNUM_RSI);
1438                if (loc.rex_byte) regs.push_back(REGNUM_R14);
1439                break;
1440             case r_EDI:
1441             case r_eDI:
1442                regs.push_back(REGNUM_RDI);
1443                if (loc.rex_byte) regs.push_back(REGNUM_R15);
1444                break;
1445             case r_EDXEAX:
1446                regs.push_back(REGNUM_RAX);
1447                regs.push_back(REGNUM_RDX);
1448                break;
1449             case r_ECXEBX:
1450                regs.push_back(REGNUM_RBX);
1451                regs.push_back(REGNUM_RCX);
1452                break;
1453          }
1454       }
1455    }
1456    return true;
1457 }
1458
1459 /**
1460  * The comments and naming schemes in this function assume some familiarity with
1461  * the IA32/IA32e instruction encoding.  If you don't understand this, I suggest
1462  * you start with Chapter 2 of:
1463  *  _IA-32 Intel Architecture Software Developer's Manual, Volume 2a_
1464  * and appendix A of:
1465  *  _IA-32 Intel Architecture Software Developer's Manual, Volume 2b_
1466  *
1467  * This function takes an instruction that accesses memory, and emits a 
1468  * copy of that instruction that has the load/store replaces with a load/store
1469  * through a register.  For example, if this function were called with 'loadExpr = r12'
1470  * on the instruction 'mov 12(%rax)->%rbx', we would emit 'mov (%r12)->%rbx'.
1471  * Note that we strip off any displacements, indexs, etc...  The register is assumed
1472  * to contain the final address that will be loaded/stored.
1473  **/
1474 bool instruction::generateMem(codeGen &gen,
1475                               Address /*origAddr*/, 
1476                               Address /*newAddr*/,
1477                               Register loadExpr,
1478                               Register storeExpr) 
1479 {
1480    /**********
1481     * Check parameters
1482     **********/
1483    Register newreg = Null_Register;
1484    if (loadExpr != Null_Register && storeExpr != Null_Register) 
1485       return false; //Can only do one memory replace per instruction now
1486    else if (loadExpr == Null_Register && storeExpr == Null_Register) 
1487       return false; //None specified
1488    else if (loadExpr != Null_Register && storeExpr == Null_Register) 
1489       newreg = loadExpr;
1490    else if (loadExpr == Null_Register && storeExpr != Null_Register) 
1491       newreg = storeExpr;
1492
1493    /********************************
1494     * Section 1.  Read the instruction into our internal data structures.
1495     ********************************/
1496    GET_PTR(insnBuf, gen);
1497    const unsigned char *insn_ptr = ptr();
1498
1499    struct ia32_memacc memacc[3];
1500    struct ia32_condition cond;
1501    struct ia32_locations loc;
1502
1503    ia32_entry *entry;
1504    ia32_instruction orig_instr(memacc, &cond, &loc);
1505    ia32_decode(IA32_DECODE_MEMACCESS | IA32_DECODE_CONDITION,
1506                insn_ptr, orig_instr);
1507    entry = orig_instr.getEntry();
1508
1509    if (gen.addrSpace()->getAddressWidth() != 8)
1510       //Currently works only on IA-32e
1511       return false; 
1512
1513    if (orig_instr.getPrefix()->getPrefix(1) != 0)
1514       //The instruction accesses memory via segment registers.  Disallow.
1515       return false;
1516    
1517    if (loc.modrm_position == -1)
1518       //Only supporting MOD/RM instructions now
1519       return false; 
1520
1521    if (loc.address_size == 1)
1522       //Don't support 16-bit instructions yet
1523       return false;
1524
1525    if (loc.modrm_reg == 4 && !loc.rex_r) {
1526       //The non-memory access register is %rsp/%esp, we can't work with
1527       // this register due to our register saving techniques.
1528       return false;
1529    }
1530
1531    if (loc.modrm_mod == 3) {
1532       //This instruction doesn't use the MOD/RM to access memory
1533       return false;
1534    }
1535    
1536    /*********************************
1537     * Section 2.  We understand the instruction.  Output it
1538     *********************************/
1539    int emit_displacement = 0;
1540    int emit_mod = 0;
1541    int emit_sib = 0;
1542    int new_sib = 0;
1543    
1544    unsigned char *walker = insnBuf;
1545    
1546    /**
1547     * Handle two special cases, where we emit a memory instruction
1548     * that loads from/to RBP/R13 or RSP/R12
1549     **/
1550    if (newreg == REGNUM_RBP || newreg == REGNUM_R13) {
1551       //You can't encode rbp or r13 normally i.e. 'mov (%r13)->%rax'
1552       // Instead we encode using a displacement, so 'mov 0(%r13)->%rax'
1553       emit_displacement = 1;
1554       emit_mod = 1; //1 encodes the 0(%reg) format
1555    }
1556    
1557    if (newreg == REGNUM_RSP || newreg == REGNUM_R12) {
1558       //You can't encode rsp or r12 normally.  We'll emit a SIB instruction.
1559       // So instead of 'mov (%r12)->%rax' we'll emit 'mov (%r12,0,0)->%rax
1560       emit_sib = 1;
1561       SIB_SET_REG(new_sib, newreg & 7);
1562       SIB_SET_INDEX(new_sib, newreg & 4); //4 encodes to no-index
1563       //SIB_SET_SS(new_sib, 0); //Gives gcc warning statement w/ no effect
1564       loc.rex_x = 0; //If we emit a rex, don't extend the index.
1565    }
1566    
1567    /**
1568     * Emit prefixes
1569     **/
1570    unsigned char new_rex = 0;
1571    
1572    //Emit all prefixes except for rex
1573    for (int i=0; i<loc.num_prefixes; i++) {
1574       if (i != loc.rex_position)
1575          *walker++ = insn_ptr[i];
1576    }
1577    
1578    //Emit the rex
1579    if (loc.rex_position != -1 || (newreg & 8)) {
1580       //If there was no REX byte, and the high bit of the new register
1581       // is set, then we'll need to make a rex byte to encode that high bit.
1582       loc.rex_b = static_cast<unsigned char>(newreg & 8);
1583       REX_INIT(new_rex);
1584       REX_SET_W(new_rex, loc.rex_w);
1585       REX_SET_R(new_rex, loc.rex_r);
1586       REX_SET_X(new_rex, loc.rex_x);
1587       REX_SET_B(new_rex, loc.rex_b); 
1588       *walker++ = new_rex;
1589    }
1590    
1591    /**
1592     * Copy opcode
1593     **/
1594    for (int i=loc.num_prefixes; i<loc.num_prefixes+(int)loc.opcode_size; i++) {
1595       *walker++ = insn_ptr[i];
1596    }
1597    
1598    /**
1599     * Emit MOD/RM byte
1600     **/
1601    unsigned char new_modrm = 0;
1602    MODRM_SET_MOD(new_modrm, emit_mod); 
1603    MODRM_SET_RM(new_modrm, newreg & 7); //The new register replacing the memaccess
1604    // Only the bottom 3 bits go here
1605    MODRM_SET_REG(new_modrm, loc.modrm_reg); //The bottom old register
1606    *walker++ = new_modrm;
1607    
1608    /**
1609     * Emit SIB byte
1610     **/
1611    if (emit_sib) {
1612       *walker++ = static_cast<unsigned char>(new_sib);
1613    }
1614    
1615    /**
1616     * Emit displacement
1617     **/
1618    if (emit_displacement) {
1619       *walker++ = 0x0; //We only need 0 displacements now.
1620    }
1621    
1622    /**
1623     * Emit immediate
1624     **/
1625    for (unsigned i=0; i<loc.imm_size; i++)
1626    {
1627       *walker++ = insn_ptr[loc.imm_position + i];
1628    }
1629
1630    //Debug output.  Fix the end of testdump.c, compile it, the do an
1631    // objdump -D
1632    /*   static FILE *f = NULL;
1633    if (f == NULL)
1634    {
1635       f = fopen("testdump.c", "w+");
1636       if (!f)
1637          perror("Couldn't open");
1638       fprintf(f, "char buffer[] = {\n");
1639    }
1640    fprintf(f, "144, 144, 144, 144, 144, 144, 144, 144, 144,\n");
1641    for (unsigned i=0; i<orig_instr.getSize(); i++) {
1642       fprintf(f, "%u, ", (unsigned) insn_ptr[i]);
1643    }
1644    fprintf(f, "\n");
1645    for (int i=0; i<(walker-insnBuf); i++) {
1646       fprintf(f, "%u, ", (unsigned) insnBuf[i]);
1647    }
1648    fprintf(f, "\n");
1649    fprintf(f, "144, 144, 144, 144, 144, 144, 144, 144, 144,\n");*/
1650    SET_PTR(walker, gen);
1651    return true;
1652 }
1653
1654 int instruction::getStackDelta()
1655 {
1656    ia32_instruction instruc;
1657    const unsigned char *p = ptr();
1658    ia32_decode(0, ptr(), instruc);
1659
1660    if (instruc.getEntry()->id == e_push)
1661       return -4;
1662    if (instruc.getEntry()->id == e_pop)
1663       return 4;
1664    if (instruc.getEntry()->id == e_pusha_d)
1665       return (-4 * 9);
1666    if (instruc.getEntry()->id == e_popa_d)
1667       return (4 * 9);
1668
1669    if (p[0] == 0x83 && p[1] == 0xec) {
1670       //Subtract byte
1671       return -1 * (signed char) p[2];
1672    }
1673
1674    if (p[0] == 0x83 && p[1] == 0xc4) {
1675       //Add byte
1676       return (signed char) p[2];
1677    }
1678    
1679    return 0;
1680 }
1681
1682 bool instruction::isNop() const
1683
1684
1685    int displacement_location = 0;
1686    int displacement_size = 0;
1687    if (!(type_ & IS_NOP)) //NOP or LEA
1688       return false;
1689
1690    if (*op_ptr_ == NOP) {
1691       return true;
1692    }
1693
1694    ia32_memacc mac[3];
1695    ia32_condition cnd;
1696    ia32_locations loc;
1697
1698    ia32_instruction instruc(mac, &cnd, &loc);
1699
1700    ia32_decode(IA32_FULL_DECODER, ptr(), instruc);
1701
1702
1703    if (instruc.getEntry()->id == e_nop) {
1704       return true;
1705    }
1706
1707    if (loc.modrm_mod == 3) {
1708       return false;
1709    }
1710    if (loc.modrm_mod == 0 && loc.modrm_rm == 5) {
1711       return false;
1712    }
1713
1714    if (loc.rex_x) {
1715       return false;
1716    }
1717    if (loc.rex_r != loc.rex_b) {
1718       return false;
1719    }
1720
1721    if (loc.disp_position != -1) {
1722       for (unsigned i=0; i<loc.disp_size; i++) {
1723          if (ptr_[i + loc.disp_position] != 0) {
1724             return false;
1725          }
1726       }
1727       displacement_location = loc.disp_position;
1728       displacement_size = loc.disp_size;
1729    }
1730    
1731    if (loc.modrm_rm == 4) {
1732       unsigned scale;
1733       Register index, base;
1734       decode_SIB(loc.sib_byte, scale, index, base);
1735       
1736       if (index != 4) {
1737          return false;
1738       }
1739
1740       if (base != loc.modrm_reg) {
1741          return false;
1742       }
1743    }
1744    else if (loc.modrm_reg != loc.modrm_rm) {
1745       return false;
1746    }
1747
1748
1749    return true;
1750 }