trevon/fold
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
fold/third_party/ghidra-decompiler/cpp/slghpatexpress.hh
trvon 5152d0c9f7
 feat(binary): vendor Ghidra 12.1 decompiler + validate P-Code lifting (Phase 0-1) 
Foundation for replacing fold's dead/abstract binary encoder with a real
SSA P-Code frontend. Verified root-cause gap: serializeBinaryIR() emits only
data-discovery nodes (sections/strings/imports/exports); the control-flow
BinaryExprKind values (BasicBlock/CallSite/...) are never constructed, so the
Z3-BB encoder's encodable filter is always empty and encodeBinaryBBs never
runs — hence 0 binary Z3 findings. The P-Code pipeline supersedes that path.

Phase 0 — docs/internal/ghidra-pcode-integration-research.md: P-Code opcode
core, the decompiler C++ embedding API (LoadImage/SleighArchitecture/Funcdata),
the CORE+DECCORE+SLEIGH source sets, no-bison finding, and pypcode as build
reference.

Phase 1 — vendored Ghidra decompiler at pinned commit (Ghidra_12.1_build,
7e89d94e34...) under third_party/ghidra-decompiler/ (cpp + AArch64 specs +
Apache-2.0 LICENSE + VENDOR.md + .gitignore for build artifacts). Validated by
hand on this clang-21/macOS toolchain:
  - full SSA engine (CORE+DECCORE+SLEIGH, 80 files incl. heritage/funcdata/
    action) compiles clean, -std=c++11 -O2, NO BFD, NO bison (generated
    parsers are committed upstream; ruleparse isn't in the lib set);
  - sleigh compiler builds; AArch64 .slaspec -> .sla compiles;
  - tools/pcode_dump.cpp (custom LoadImage, no BFD) lifts the real arm64
    sym._div_by_zero_direct to correct P-Code: `mov w9,#0 -> COPY(const 0)`,
    `sdiv -> INT_SDIV(w8,w9)` — divisor zero-ness explicit in the data flow,
    so the Phase-3 encoder proves div-by-zero trivially, multi-arch.

Not yet meson-wired (next step) and no fold-side IR/encoder yet (Phase 2-3);
this commit is the validated vendor + smoke tool.

Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
2026-05-31 17:32:47 -04:00

490 lines
20 KiB
C++
Raw Permalink Blame History

/* ###
* IP: GHIDRA
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef __SLGHPATEXPRESS_HH__
#define __SLGHPATEXPRESS_HH__
#include "slghpattern.hh"
namespace ghidra {
class TokenPattern {
Pattern *pattern;
vector<Token *> toklist;
bool leftellipsis;
bool rightellipsis;
static PatternBlock *buildSingle(int4 startbit,int4 endbit,uintm byteval);
static PatternBlock *buildBigBlock(int4 size,int4 bitstart,int4 bitend,intb value);
static PatternBlock *buildLittleBlock(int4 size,int4 bitstart,int4 bitend,intb value);
int4 resolveTokens(const TokenPattern &tokpat1,const TokenPattern &tokpat2);
TokenPattern(Pattern *pat) { pattern = pat; leftellipsis=false; rightellipsis=false; }
public:
TokenPattern(void); // TRUE pattern unassociated with a token
TokenPattern(bool tf); // TRUE or FALSE pattern unassociated with a token
TokenPattern(Token *tok); // TRUE pattern associated with token -tok-
TokenPattern(Token *tok,intb value,int4 bitstart,int4 bitend);
TokenPattern(intb value,int4 startbit,int4 endbit);
TokenPattern(const TokenPattern &tokpat);
~TokenPattern(void) { delete pattern; }
const TokenPattern &operator=(const TokenPattern &tokpat);
void setLeftEllipsis(bool val) { leftellipsis = val; }
void setRightEllipsis(bool val) { rightellipsis = val; }
bool getLeftEllipsis(void) const { return leftellipsis; }
bool getRightEllipsis(void) const { return rightellipsis; }
TokenPattern doAnd(const TokenPattern &tokpat) const;
TokenPattern doOr(const TokenPattern &tokpat) const;
TokenPattern doCat(const TokenPattern &tokpat) const;
TokenPattern commonSubPattern(const TokenPattern &tokpat) const;
Pattern *getPattern(void) const { return pattern; }
int4 getMinimumLength(void) const;
bool alwaysTrue(void) const { return pattern->alwaysTrue(); }
bool alwaysFalse(void) const { return pattern->alwaysFalse(); }
bool alwaysInstructionTrue(void) const { return pattern->alwaysInstructionTrue(); }
};
class PatternValue;
class PatternExpression {
int4 refcount; // Number of objects referencing this
// for deletion
protected:
virtual ~PatternExpression(void) {} // Only delete through release
public:
PatternExpression(void) { refcount = 0; }
virtual intb getValue(ParserWalker &walker) const=0;
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const=0;
virtual void listValues(vector<const PatternValue *> &list) const=0;
virtual void getMinMax(vector<intb> &minlist,vector<intb> &maxlist) const=0;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const=0;
virtual void encode(Encoder &encoder) const=0;
virtual void decode(Decoder &decoder,Translate *trans)=0;
intb getSubValue(const vector<intb> &replace) {
int4 listpos = 0;
return getSubValue(replace,listpos); }
void layClaim(void) { refcount += 1; }
static void release(PatternExpression *p);
static PatternExpression *decodeExpression(Decoder &decoder,Translate *trans);
};
class PatternValue : public PatternExpression {
public:
virtual TokenPattern genPattern(intb val) const=0;
virtual void listValues(vector<const PatternValue *> &list) const { list.push_back(this); }
virtual void getMinMax(vector<intb> &minlist,vector<intb> &maxlist) const {
minlist.push_back(minValue()); maxlist.push_back(maxValue()); }
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const { return replace[listpos++]; }
virtual intb minValue(void) const=0;
virtual intb maxValue(void) const=0;
};
class TokenField : public PatternValue {
Token *tok;
bool bigendian;
bool signbit;
int4 bitstart,bitend; // Bits within the token, 0 bit is LEAST significant
int4 bytestart,byteend; // Bytes to read to get value
int4 shift; // Amount to shift to align value (bitstart % 8)
public:
TokenField(void) {} // For use with decode
TokenField(Token *tk,bool s,int4 bstart,int4 bend);
virtual intb getValue(ParserWalker &walker) const;
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(tok); }
virtual TokenPattern genPattern(intb val) const;
virtual intb minValue(void) const { return 0; }
virtual intb maxValue(void) const { intb res=0; return zero_extend(~res,bitend-bitstart); }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class ContextField : public PatternValue {
int4 startbit,endbit;
int4 startbyte,endbyte;
int4 shift;
bool signbit;
public:
ContextField(void) {} // For use with decode
ContextField(bool s,int4 sbit,int4 ebit);
int4 getStartBit(void) const { return startbit; }
int4 getEndBit(void) const { return endbit; }
bool getSignBit(void) const { return signbit; }
virtual intb getValue(ParserWalker &walker) const;
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual TokenPattern genPattern(intb val) const;
virtual intb minValue(void) const { return 0; }
virtual intb maxValue(void) const { intb res=0; return zero_extend(~res,(endbit-startbit)); }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class ConstantValue : public PatternValue {
intb val;
public:
ConstantValue(void) {} // For use with decode
ConstantValue(intb v) { val = v; }
virtual intb getValue(ParserWalker &walker) const { return val; }
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual TokenPattern genPattern(intb v) const { return TokenPattern(val==v); }
virtual intb minValue(void) const { return val; }
virtual intb maxValue(void) const { return val; }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class StartInstructionValue : public PatternValue {
public:
StartInstructionValue(void) {}
virtual intb getValue(ParserWalker &walker) const {
return (intb)AddrSpace::byteToAddress(walker.getAddr().getOffset(),walker.getAddr().getSpace()->getWordSize()); }
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual TokenPattern genPattern(intb val) const { return TokenPattern(); }
virtual intb minValue(void) const { return (intb)0; }
virtual intb maxValue(void) const { return (intb)0; }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class EndInstructionValue : public PatternValue {
public:
EndInstructionValue(void) {}
virtual intb getValue(ParserWalker &walker) const {
return (intb)AddrSpace::byteToAddress(walker.getNaddr().getOffset(),walker.getNaddr().getSpace()->getWordSize()); }
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual TokenPattern genPattern(intb val) const { return TokenPattern(); }
virtual intb minValue(void) const { return (intb)0; }
virtual intb maxValue(void) const { return (intb)0; }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class Next2InstructionValue : public PatternValue {
public:
Next2InstructionValue(void) {}
virtual intb getValue(ParserWalker &walker) const {
return (intb)AddrSpace::byteToAddress(walker.getN2addr().getOffset(),walker.getN2addr().getSpace()->getWordSize()); }
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual TokenPattern genPattern(intb val) const { return TokenPattern(); }
virtual intb minValue(void) const { return (intb)0; }
virtual intb maxValue(void) const { return (intb)0; }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class Constructor; // Forward declaration
class OperandSymbol;
class OperandValue : public PatternValue {
int4 index; // This is the defining field of expression
Constructor *ct; // cached pointer to constructor
public:
OperandValue(void) { } // For use with decode
OperandValue(int4 ind,Constructor *c) { index = ind; ct = c; }
void changeIndex(int4 newind) { index = newind; }
bool isConstructorRelative(void) const;
const string &getName(void) const;
virtual TokenPattern genPattern(intb val) const;
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return ops[index]; }
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual intb minValue(void) const;
virtual intb maxValue(void) const;
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class BinaryExpression : public PatternExpression {
PatternExpression *left,*right;
protected:
virtual ~BinaryExpression(void);
public:
BinaryExpression(void) { left = (PatternExpression *)0; right = (PatternExpression *)0; } // For use with decode
BinaryExpression(PatternExpression *l,PatternExpression *r);
PatternExpression *getLeft(void) const { return left; }
PatternExpression *getRight(void) const { return right; }
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual void listValues(vector<const PatternValue *> &list) const {
left->listValues(list); right->listValues(list); }
virtual void getMinMax(vector<intb> &minlist,vector<intb> &maxlist) const {
left->getMinMax(minlist,maxlist); right->getMinMax(minlist,maxlist); }
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class UnaryExpression : public PatternExpression {
PatternExpression *unary;
protected:
virtual ~UnaryExpression(void);
public:
UnaryExpression(void) { unary = (PatternExpression *)0; } // For use with decode
UnaryExpression(PatternExpression *u);
PatternExpression *getUnary(void) const { return unary; }
virtual TokenPattern genMinPattern(const vector<TokenPattern> &ops) const { return TokenPattern(); }
virtual void listValues(vector<const PatternValue *> &list) const {
unary->listValues(list); }
virtual void getMinMax(vector<intb> &minlist,vector<intb> &maxlist) const {
unary->getMinMax(minlist,maxlist);
}
virtual void encode(Encoder &encoder) const;
virtual void decode(Decoder &decoder,Translate *trans);
};
class PlusExpression : public BinaryExpression {
public:
PlusExpression(void) {} // For use by decode
PlusExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class SubExpression : public BinaryExpression {
public:
SubExpression(void) {} // For use with decode
SubExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class MultExpression : public BinaryExpression {
public:
MultExpression(void) {} // For use with decode
MultExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class LeftShiftExpression : public BinaryExpression {
public:
LeftShiftExpression(void) {}
LeftShiftExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class RightShiftExpression : public BinaryExpression {
public:
RightShiftExpression(void) {}
RightShiftExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class AndExpression : public BinaryExpression {
public:
AndExpression(void) {}
AndExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class OrExpression : public BinaryExpression {
public:
OrExpression(void) {}
OrExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class XorExpression : public BinaryExpression {
public:
XorExpression(void) {}
XorExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class DivExpression : public BinaryExpression {
public:
DivExpression(void) {}
DivExpression(PatternExpression *l,PatternExpression *r) : BinaryExpression(l,r) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class MinusExpression : public UnaryExpression {
public:
MinusExpression(void) {}
MinusExpression(PatternExpression *u) : UnaryExpression(u) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
class NotExpression : public UnaryExpression {
public:
NotExpression(void) {}
NotExpression(PatternExpression *u) : UnaryExpression(u) {}
virtual intb getValue(ParserWalker &walker) const;
virtual intb getSubValue(const vector<intb> &replace,int4 &listpos) const;
virtual void encode(Encoder &encoder) const;
};
struct OperandResolve {
vector<OperandSymbol *> &operands;
OperandResolve(vector<OperandSymbol *> &ops) : operands(ops) {
base=-1; offset=0; cur_rightmost = -1; size = 0; }
int4 base; // Current base operand (as we traverse the pattern equation from left to right)
int4 offset; // Bytes we have traversed from the LEFT edge of the current base
int4 cur_rightmost; // (resulting) rightmost operand in our pattern
int4 size; // (resulting) bytes traversed from the LEFT edge of the rightmost
};
// operandOrder returns a vector of the self-defining OperandSymbols as the appear
// in left to right order in the pattern
class PatternEquation {
int4 refcount; // Number of objects referencing this
protected:
mutable TokenPattern resultpattern; // Resulting pattern generated by this equation
virtual ~PatternEquation(void) {} // Only delete through release
public:
PatternEquation(void) { refcount = 0; }
const TokenPattern &getTokenPattern(void) const { return resultpattern; }
virtual void genPattern(const vector<TokenPattern> &ops) const=0;
virtual bool resolveOperandLeft(OperandResolve &state) const=0;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const {}
void layClaim(void) { refcount += 1; }
static void release(PatternEquation *pateq);
};
class OperandEquation : public PatternEquation { // Equation that defines operand
int4 index;
public:
OperandEquation(int4 ind) { index = ind; }
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const;
};
class UnconstrainedEquation : public PatternEquation { // Unconstrained equation, just get tokens
PatternExpression *patex;
protected:
virtual ~UnconstrainedEquation(void);
public:
UnconstrainedEquation(PatternExpression *p);
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
};
class ValExpressEquation : public PatternEquation {
protected:
PatternValue *lhs;
PatternExpression *rhs;
virtual ~ValExpressEquation(void);
public:
ValExpressEquation(PatternValue *l,PatternExpression *r);
virtual bool resolveOperandLeft(OperandResolve &state) const;
};
class EqualEquation : public ValExpressEquation {
public:
EqualEquation(PatternValue *l,PatternExpression *r) : ValExpressEquation(l,r) {}
virtual void genPattern(const vector<TokenPattern> &ops) const;
};
class NotEqualEquation : public ValExpressEquation {
public:
NotEqualEquation(PatternValue *l,PatternExpression *r) : ValExpressEquation(l,r) {}
virtual void genPattern(const vector<TokenPattern> &ops) const;
};
class LessEquation : public ValExpressEquation {
public:
LessEquation(PatternValue *l,PatternExpression *r) : ValExpressEquation(l,r) {}
virtual void genPattern(const vector<TokenPattern> &ops) const;
};
class LessEqualEquation : public ValExpressEquation {
public:
LessEqualEquation(PatternValue *l,PatternExpression *r) : ValExpressEquation(l,r) {}
virtual void genPattern(const vector<TokenPattern> &ops) const;
};
class GreaterEquation : public ValExpressEquation {
public:
GreaterEquation(PatternValue *l,PatternExpression *r) : ValExpressEquation(l,r) {}
virtual void genPattern(const vector<TokenPattern> &ops) const;
};
class GreaterEqualEquation : public ValExpressEquation {
public:
GreaterEqualEquation(PatternValue *l,PatternExpression *r) : ValExpressEquation(l,r) {}
virtual void genPattern(const vector<TokenPattern> &ops) const;
};
class EquationAnd : public PatternEquation { // Pattern Equations ANDed together
PatternEquation *left;
PatternEquation *right;
protected:
virtual ~EquationAnd(void);
public:
EquationAnd(PatternEquation *l,PatternEquation *r);
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const;
};
class EquationOr : public PatternEquation { // Pattern Equations ORed together
PatternEquation *left;
PatternEquation *right;
protected:
virtual ~EquationOr(void);
public:
EquationOr(PatternEquation *l,PatternEquation *r);
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const;
};
class EquationCat : public PatternEquation { // Pattern Equations concatenated
PatternEquation *left;
PatternEquation *right;
protected:
virtual ~EquationCat(void);
public:
EquationCat(PatternEquation *l,PatternEquation *r);
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const;
};
class EquationLeftEllipsis : public PatternEquation { // Equation preceded by ellipses
PatternEquation *eq;
protected:
virtual ~EquationLeftEllipsis(void) { PatternEquation::release(eq); }
public:
EquationLeftEllipsis(PatternEquation *e) { (eq=e)->layClaim(); }
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const;
};
class EquationRightEllipsis : public PatternEquation { // Equation preceded by ellipses
PatternEquation *eq;
protected:
virtual ~EquationRightEllipsis(void) { PatternEquation::release(eq); }
public:
EquationRightEllipsis(PatternEquation *e) { (eq=e)->layClaim(); }
virtual void genPattern(const vector<TokenPattern> &ops) const;
virtual bool resolveOperandLeft(OperandResolve &state) const;
virtual void operandOrder(Constructor *ct,vector<OperandSymbol *> &order) const;
};
} // End namespace ghidra
#endif
Reference in a new issue View git blame Copy permalink