PatternDeobfuscate.cpp

#include <hexrays.hpp>
#include "HexRaysUtil.hpp"
#include "PatternDeobfuscateUtil.hpp"
#include "Config.hpp"

// Our pattern-based deobfuscation is implemented as an optinsn_t structure,
// which allows us to hook directly into the microcode generation phase and
// perform optimizations automatically, whenever code is decompiled.
struct ObfCompilerOptimizer : public optinsn_t
{
	// This function simplifies microinstruction patterns that look like
	// either: (x & 1) | (y & 1) ==> (x | y) & 1
	// or:     (x & 1) ^ (y & 1) ==> (x ^ y) & 1
	// Though it may not seem like much of an "obfuscation" or "deobfuscation"
	// technique on its own, getting rid of the "&1" terms helps reveal other
	// patterns so they can be deobfuscated.
	int pat_LogicAnd1(minsn_t *ins, mblock_t * /*blk*/)
	{
		// Only applies to OR / XOR microinstructions
		if (ins->opcode != m_or && ins->opcode != m_xor)
			return 0;

		// Only applies when the operands are results of other
		// microinstructions (since, after all, we are expecting them to be
		// ANDed by 1, which is represented in terms of a microinstruction
		// provider mop_d operand).
		if (ins->l.t != mop_d || ins->r.t != mop_d)
			return 0;

		minsn_t *insLeft, *insRight;
		mop_t *opLeft, *opRight;

		// Get rid of & 1. bLeft1 is true if there was an &1.
		bool bLeft1 = TunnelThroughAnd1(ins->l.d, insLeft, true, &opLeft);
		if (!bLeft1)
			return 0;

		// Same for right-hand side
		bool bRight1 = TunnelThroughAnd1(ins->r.d, insRight, true, &opRight);
		if (!bRight1)
			return 0;

		// If we get here, then the pattern matched.
		// Move the logical operation (OR or XOR) to the left-hand side,
		// with the operands that have the &1 removed.
		ins->l.d->opcode = ins->opcode;
		ins->l.d->l.swap(*opLeft);
		ins->l.d->r.swap(*opRight);

		// Change the top-level instruction from OR or XOR to AND, and set the
		// right-hand side to the 1-bit constant value 1.
		ins->opcode = m_and;
		ins->r.make_number(1, 1);

		// msg("[I] pat_LogicAnd1\n");
		// Return 1 to indicate that we changed the instruction.
		return 1;
	}

	// One of the obfuscation patterns involves a subtraction by 1. In the
	// assembly code, this is implemented by something like:
	//
	// add eax, 2
	// add eax, ecx ; or whatever
	// sub eax, 3
	//
	// Usually, Hex-Rays will automatically simplify this to (eax+ecx)-1.
	// However, I did experience situations where Hex-Rays still represented
	// the decompiled output as 2+(eax+ecx)-3. This function, then, determines
	// when Hex-Rays has represented the subtraction as just mentioned. If so,
	// it extracts the term that is being subtracted by 1.
	bool pat_IsSubBy1(minsn_t *ins, mop_t *&op) const
	{
		// We're looking for x+(y-z), where x and z are numeric
		if (ins->opcode != m_add)
			return false;

		// Extract x and (y-z)
		mop_t *opAddNum = NULL, *opAddNonNum = NULL;
		if (!ExtractNumAndNonNum(ins, opAddNum, opAddNonNum))
			return false;

		// Ensure that the purported (y-z) term actually is a subtraction
		if (opAddNonNum->t != mop_d || opAddNonNum->d->opcode != m_sub)
			return false;

		// Extract y and z. I guess technically I shouldn't use
		// ExtractNumAndNonNum here since subtraction isn't commutative...
		// Call that a bug, but it didn't matter in practice.
		mop_t *opSubNum = NULL, *opSubNonNum = NULL;
		if (!ExtractNumAndNonNum(opAddNonNum->d, opSubNum, opSubNonNum))
			return false;

		// Pass y back to the caller
		op = opSubNonNum;

		// x-z must be -1, or, equivalently, z-x must be 1.
		return (opSubNum->nnn->value - opAddNum->nnn->value) == 1LL;
	}

	// This function performs the following pattern-substitution:
	// (x * (x-1)) & 1 ==> 0
	int pat_MulSub(minsn_t *andIns, mblock_t *blk)
	{
		// Topmost term has to be &1. The 1 is not required to be 1-byte large.
		minsn_t *ins = andIns;
		if (!TunnelThroughAnd1(ins, ins, false))
			return 0;

		// Looking for multiplication terms
		if (ins->opcode != m_mul)
			return 0;

		// We have two different mechanisms for determining if there is a
		// subtraction by 1.
		bool bWasSubBy1 = false;

		// Ultimately, we need to find thse things:
		minsn_t *insSub;    // Subtraction instruction x-1
		mop_t *opMulNonSub; // Operand of multiply that isn't a subtraction
		mop_t *subNonNum = NULL;   // x from the x-1 instruction

		// Try first method for locating subtraction by 1, i.e., simply
		// subtraction by the constant number 1.
		do
		{
			// Find the subtraction subterm of the multiplication
			if (!ExtractByOpcodeType(ins, m_sub, insSub, opMulNonSub))
				break;

			mop_t *subNum;
			// Find the numeric part of the subtraction. Again, I shouldn't use
			// ExtractNumAndNonNum here since subtraction isn't commutative.
			if (!ExtractNumAndNonNum(insSub, subNum, subNonNum))
				break;

			// Ensure that the subtraction amount is 1.
			if (subNum->nnn->value != 1)
				break;

			// Indicate that we successfully found the subtraction.
			bWasSubBy1 = true;
		} while (0);

		// If we didn't find the subtraction, see if we have an add/sub pair
		// instead, which totals to subtraction minus one.
		if (!bWasSubBy1)
		{
			// Find the ADD subterm of the multiplication. If this fails, both
			// methods failed to find the pattern, so return.
			// modified: not return for data flow tracking
			if (ExtractByOpcodeType(ins, m_add, insSub, opMulNonSub))
			{
				// Call the previous function to determine whether the ADD
				// implements a subtraction by 1.
				bWasSubBy1 = pat_IsSubBy1(insSub, subNonNum);
			}
		}

		// If both methods failed, bail.
		if (!bWasSubBy1)
		{
			// data flow tracking for each y and (x - 1) operands
			if (blk == NULL || !TraceAndExtractOpsMovAndSubBy1(blk, opMulNonSub, subNonNum, ins))
				return 0;
		}

		// We know we're dealing with (x-1) * y. ensure x==y.
		if (!equal_mops_ignore_size(*opMulNonSub, *subNonNum))
			return 0;

		// If we get here, the pattern matched.
		// Replace the whole multiplication instruction by 0.
		ins->l.make_number(0, ins->l.size);
#if IDA_SDK_VERSION == 710
		andIns->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		if (blk)
			blk->optimize_insn(andIns);
		else
			andIns->optimize_solo();
#endif
		// msg("[I] pat_MulSub\n");
		return 1;
	}

	// check y * (x - 1) and extract the operands
	// mop_t *opMulNonSub; // Operand y of multiply that isn't a subtraction
	// mop_t *subNonNum;   // Operand x from the x-1 instruction
	bool CheckAndExtractOpsSubBy1(minsn_t *ins, mop_t *&opMulNonSub, mop_t *&subNonNum)
	{
		minsn_t *insSub;    // Subtraction instruction x-1

		// Try first method for locating subtraction by 1, i.e., simply
		// subtraction by the constant number 1.
		do
		{
			// Find the subtraction subterm of the multiplication
			if (!ExtractByOpcodeType(ins, m_sub, insSub, opMulNonSub))
				break;

			mop_t *subNum;
			// Find the numeric part of the subtraction. Again, I shouldn't use
			// ExtractNumAndNonNum here since subtraction isn't commutative.
			if (!ExtractNumAndNonNum(insSub, subNum, subNonNum))
				break;

			// Ensure that the subtraction amount is 1.
			if (subNum->nnn->value != 1)
				break;

			// Indicate that we successfully found the subtraction.
			return true;
		} while (0);

		// If we didn't find the subtraction, see if we have an add/sub pair
		// instead, which totals to subtraction minus one.

		// Find the ADD subterm of the multiplication. If this fails, both
		// methods failed to find the pattern, so return.
		if (!ExtractByOpcodeType(ins, m_add, insSub, opMulNonSub))
			return false;

		// Call the previous function to determine whether the ADD
		// implements a subtraction by 1.
		return pat_IsSubBy1(insSub, subNonNum);
	}

	// This function performs the following pattern-substitution:
	// ~(x * (x - 1)) | -2 ==> -1
	int pat_MulSub2(minsn_t *orIns, mblock_t *blk)
	{
		// Topmost term has to be |-2.
		minsn_t *ins = orIns;
		if (!TunnelThroughOrMinus2(ins, ins, false))
			return 0;
		if (ins->opcode != m_xdu)
			return 0;

		// extract the subinstructions
		minsn_t *insBnot, *insMul;
		if (!ins->l.is_insn() || ins->l.d->opcode != m_bnot)
			return 0;
		insBnot = ins->l.d;
		if (!insBnot->l.is_insn() || insBnot->l.d->opcode != m_mul)
		{
			mop_t *op = &insBnot->l;
			// data flow tracking #1 for y * (x - 1) instruction
			if (blk == NULL || !FindInsWithTheOp(blk, op, insBnot, insMul, m_mul))
				return 0;
		}
		else
			insMul = insBnot->l.d; // m_mul

		// get y *(x-1)
		mop_t *opMulNonSub; // Operand y of multiply that isn't a subtraction
		mop_t *subNonNum;   // Operand x from the x-1 instruction
		if (!CheckAndExtractOpsSubBy1(insMul, opMulNonSub, subNonNum))
		{
			if (blk == NULL)
				return 0;
			// data flow tracking #2: both of the operands are not extracted due to lack of nested sub instruction
			//msg("pat_MulSub2: tracking #2 OR ins %#a at %#a\n", orIns->ea, blk->mba->entry_ea);
			if (!TraceAndExtractOpsMovAndSubBy1(blk, opMulNonSub, subNonNum, insMul))
				return 0;
		}

		// ensure x==y
		if (!equal_mops_ignore_size(*opMulNonSub, *subNonNum))
		{
			if (blk == NULL)
				return 0;
			// data flow tracking #3: both of the operands are extracted but different due to assignment to registers
			//msg("pat_MulSub2: tracking #3 OR ins %#a at %#a\n", orIns->ea, blk->mba->entry_ea);
			minsn_t *insMov;
			if (opMulNonSub->t != mop_v && FindInsWithTheOp(blk, opMulNonSub, insMul, insMov, m_mov))
				opMulNonSub = &insMov->l;
			if (subNonNum->t != mop_v && FindInsWithTheOp(blk, subNonNum, insMul, insMov, m_mov))
				subNonNum = &insMov->l;
			if (!equal_mops_ignore_size(*opMulNonSub, *subNonNum))
				return 0;
		}

		// If we get here, the pattern matched.
		// Replace the whole multiplication instruction by 0.
		//ins->l.make_number(0, ins->l.size);
		insBnot->l.make_number(2, insBnot->l.size); // m_bnot operand to be modified with 2
#if IDA_SDK_VERSION == 710
		orIns->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		if (blk)
			blk->optimize_insn(orIns);
		else
			orIns->optimize_solo();
#endif
		//msg("[I] pat_MulSub2\n");
		return 1;
	}

	// This function replaces read-only initialized global variable patterns with 0 in m_setl/m_jl/m_jge, m_seto (MMAT_CALLS or later only)
	// either: dword_73FBB588 >= immediate value (e.g., 10, 9)
	// or:     dword_73FBB588 < immediate value (e.g., 10, 9)
	int pat_InitedVarCondImm(minsn_t *&ins, mblock_t *blk)
	{
		if (ins->opcode == m_seto && (blk == NULL || blk->mba->maturity <= MMAT_LOCOPT))
			return 0;

		mop_t *condNum;
		mop_t *condNonNum;
		if (!ExtractNumAndNonNum(ins, condNum, condNonNum))
			return 0;

		//if (condNum->nnn->value != 10)
		if (condNum->nnn->value != 10 && condNum->nnn->value != 9)
			return 0;

		if (condNonNum->t == mop_v)
		{
			if (!IsReadOnlyInitedVar(condNonNum))
				return 0;
		}
		else
		{
			if (blk == NULL)
				return 0;
			// data flow tracking
			minsn_t *insOut;
			if (!FindInsWithTheOp(blk, condNonNum, ins, insOut, m_mov, mop_v))
				return 0;
			if (!IsReadOnlyInitedVar(&insOut->l))
				return 0;
			//else
				//msg("pat_InitedVarCondImm: tracked ins %a at %a\n", ins->ea, blk->mba->entry_ea);
		}

		// Replace the global variable with 0
		if (equal_mops_ignore_size(ins->l, *condNonNum))
			ins->l.make_number(0, ins->l.size);
		else
			ins->r.make_number(0, ins->r.size);
#if IDA_SDK_VERSION == 710
		ins->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		if (blk)
			blk->optimize_insn(ins);
		else
			ins->optimize_solo();
#endif
		return 1;
	}

	// This function replaces read-only initialized global variable patterns with 0 in m_sets (MMAT_CALLS or later only)
	// either: dword_73FBB588 - 10 >= 0
	// or:     dword_10020CE4 - 10 < 0
	int pat_InitedVarSubImmCond0(minsn_t *ins, mblock_t *blk)
	{
		if (blk == NULL || blk->mba->maturity <= MMAT_LOCOPT)
			return 0;

		minsn_t *insSub;
		if (!ins->l.is_insn() || ins->l.d->opcode != m_sub)
			return 0;
		insSub = ins->l.d;

		int ret = pat_InitedVarCondImm(insSub, blk);
		if (ret && insSub->opcode == m_nop)
		{
			ins->opcode = m_mov;
			ins->l.make_number(1, 1);
			if (blk)
				blk->optimize_insn(ins);
			else
				ins->optimize_solo();
			return 1;
		}
		return 0;
	}

	// This function replaces read-only initialized global variable patterns with 0
	// e.g.,
	// v10 = dword_73FBB590;
	// if ( v10 < 10 )
	//     ....
	int pat_InitedVarMov(minsn_t *ins)
	{
		if (!IsReadOnlyInitedVar(&ins->l))
			return 0;

		// Replace the global variable with 0
		ins->l.make_number(0, ins->l.size);
#if IDA_SDK_VERSION == 710
		ins->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		ins->optimize_solo();
		//blk->optimize_insn(ins);
#endif
		return 1;
	}

	// This function looks tries to replace patterns of the form
	// either: (x&y)|(x^y)   ==> x|y
	// or:     (x&y)|(y^x)   ==> x|y
	int pat_OrViaXorAnd(minsn_t *ins, mblock_t *blk)
	{
#if OPTVERBOSE
		qstring qIns;
		ins->print(&qIns);
		msg("Trying to optimize jcc cond: %s\n", qIns.c_str());
#endif
		// Looking for OR instructions...
		if (ins->opcode != m_or)
			return 0;

		// ... where one side is a compound XOR, and the other is not ...
		minsn_t *xorInsn;
		mop_t *nonXorOp;
		if (!ExtractByOpcodeType(ins, m_xor, xorInsn, nonXorOp))
			return 0;

		// .. and the other side is a compound AND ...
		if (nonXorOp->t != mop_d || nonXorOp->d->opcode != m_and)
			return 0;

		// Extract the operands for the AND and XOR terms
		mop_t *xorOp1 = &xorInsn->l, *xorOp2 = &xorInsn->r;
		mop_t *andOp1 = &nonXorOp->d->l, *andOp2 = &nonXorOp->d->r;

		// The operands must be equal
		if (!(equal_mops_ignore_size(*xorOp1, *andOp1) && equal_mops_ignore_size(*xorOp2, *andOp2)) ||
 			 (equal_mops_ignore_size(*xorOp1, *andOp2) && equal_mops_ignore_size(*xorOp2, *andOp1)))
			return 0;

		// Move the operands up to the top-level OR instruction
		ins->l.swap(*xorOp1);
		ins->r.swap(*xorOp2);
#if IDA_SDK_VERSION == 710
		ins->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		if (blk)
			blk->optimize_insn(ins);
		else
			ins->optimize_solo();
#endif
		// msg("[I] pat_OrViaXorAnd\n");
		return 1;
	}

	// This pattern replaces microcode of the form (x|!x), where x is a
	// conditional, and !x is its syntactically-negated version, with 1.
	int pat_OrNegatedSameCondition(minsn_t *ins, mblock_t *blk)
	{
#if OPTVERBOSE
		qstring qIns;
		ins->print(&qIns);
		msg("Trying to optimize jcc cond: %s\n", qIns.c_str());
#endif
		// Only applies to (x|y)
		if (ins->opcode != m_or)
			return 0;

		// Only applies when x and y are compound expressions, i.e., results
		// of other microcode instructions.
		if (ins->l.t != mop_d || ins->r.t != mop_d)
			return 0;

		// Ensure x and y are syntactically-opposite versions of the same
		// conditional.
		if (!AreConditionsOpposite(ins->l.d, ins->r.d))
			return 0;

		// If we get here, the pattern matched. Replace both sides of OR with
		// 1, and then call optimize_flat to fold the constants.
		ins->l.make_number(1, 1);
		ins->r.make_number(1, 1);
#if IDA_SDK_VERSION == 710
		ins->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		if (blk)
			blk->optimize_insn(ins);
		else
			ins->optimize_solo();
#endif
		// msg("[I] pat_OrNegatedSameCondition\n");
		return 1;
	}

	// Replace patterns of the form (x&c)|(~x&d) (when c and d are numbers such
	// that c == ~d) with x^d.
	int pat_OrAndNot(minsn_t *ins, mblock_t * /*blk*/)
	{
		// Looking for OR instructions...
		if(ins->opcode != m_or)
			return 0;

		// ... with compound operands ...
		if (ins->l.t != mop_d || ins->r.t != mop_d)
			return 0;

		minsn_t *lhs1 = ins->l.d;
		minsn_t *rhs1 = ins->r.d;

		// ... where each operand is an AND ...
		if (lhs1->opcode != m_and || rhs1->opcode != m_and)
			return 0;

		// Extract the numeric and non-numeric operands from both AND terms
		mop_t *lhsNum = NULL, *rhsNum = NULL;
		mop_t *lhsNonNum = NULL, *rhsNonNum = NULL;
		bool bLhsSucc = ExtractNumAndNonNum(lhs1, lhsNum, lhsNonNum);
		bool bRhsSucc = ExtractNumAndNonNum(rhs1, rhsNum, rhsNonNum);

		// ... both AND terms must have one constant ...
		if (!bLhsSucc || !bRhsSucc)
			return 0;

		// .. both constants have a size, and are the same size ...
		if (lhsNum->size == NOSIZE || lhsNum->size != rhsNum->size)
			return 0;

		// ... and the constants are bitwise inverses of one another ...
		if ((lhsNum->nnn->value & rhsNum->nnn->value) != 0)
			return 0;

		// One of the non-numeric parts must have a binary not (i.e., ~) on it
		mop_t *nonNottedInsn = NULL, *nottedNum = NULL, *nottedInsn = NULL;

		// Check the left-hand size for binary not
		if (lhsNonNum->t == mop_d && lhsNonNum->d->opcode == m_bnot)
		{
			// Extract the NOTed term
			nottedInsn = &lhsNonNum->d->l;
			// Make note of the corresponding constant value
			nottedNum = lhsNum;
		}
		else
			nonNottedInsn = lhsNonNum;

		// Check the left-hand size for binary not
		if (rhsNonNum->t == mop_d && rhsNonNum->d->opcode == m_bnot)
		{
			// Both sides NOT? Not what we want, return 0
			if (nottedInsn != NULL)
				return 0;

			// Extract the NOTed term
			nottedInsn = &rhsNonNum->d->l;
			// Make note of the corresponding constant value
			nottedNum = rhsNum;
		}
		else
		{
			// Neither side has a NOT? Bail
			if (nonNottedInsn != NULL)
				return 0;
			nonNottedInsn = rhsNonNum;
		}

		// The expression that was NOTed must match the non-NOTed operand
		if (!equal_mops_ignore_size(*nottedInsn, *nonNottedInsn))
			return 0;

		// Okay, all of our conditions matched. Make an XOR(x,d) instruction
		ins->opcode = m_xor;
		ins->l.swap(*nonNottedInsn);
		ins->r.swap(*nottedNum);
		// msg("[I] pat_OrAndNot\n");
		return 1;
	}

	// Remove XOR chains with common terms. E.g. x^5^y^6^5^x ==> y^6.
	// This uses the XorSimplifier class from PatternDeobfuscateUtil.
	int pat_XorChain(minsn_t *ins, mblock_t *blk)
	{
		if (ins->opcode != m_xor)
			return 0;

#if OPTVERBOSE
		qstring qInsBefore, qInsAfter;
		ins->print(&qInsBefore);
#endif

		// Automagically find duplicated expressions and erase them
		XorSimplifier xs;
		if (!xs.Simplify(ins, blk))
			return 0;

#if OPTVERBOSE
		ins->print(&qInsAfter);
		msg("[I] Optimized XOR from:\n\t%s\nto:\t%s\n", qInsBefore.c_str(), qInsAfter.c_str());
#endif
		// msg("[I] pat_XorChain\n");
		return 1;

	}

	// Compare two sets of mop_t * element-by-element. Return true if they match.
	bool NonConstSetsMatch(std::set<mop_t *> *s1, std::set<mop_t *> *s2)
	{
		// Iterate over one set
		for (auto eL : *s1)
		{
			bool bFound = false;
			// Iterate over the other set
			for (auto eR : *s2)
			{
				// Compare the element from the first set against the ones in
				// the other set.
				if (equal_mops_ignore_size(*eL, *eR))
				{
					bFound = true;
					break;
				}
			}
			// If we can't find some element from the first set in the other, we're done
			if (!bFound)
				return false;
		}
		// All elements matched
		return true;
	}

	// Compare two sets of mop_t * (number values) element-by-element. There
	// should be one value in the larger set that's not in the smaller set.
	// Find and return it if that's the case.
	mop_t *FindNonCommonConstant(std::set<mop_t *> *smaller, std::set<mop_t *> *bigger)
	{
		mop_t *noMatch = NULL;
		// Iterate through the larger set
		for (auto eL : *bigger)
		{
			bool bFound = false;
			// Find each element in the smaller set
			for (auto eR : *smaller)
			{
				if (equal_mops_ignore_size(*eL, *eR))
				{
					bFound = true;
					break;
				}
			}
			// We're looking for one constant in the larger set that isn't
			// present in the smaller set.
			if (!bFound)
			{
				// If noMatch was not NULL, then there was more than one
				// constant in the larger set that wasn't in the smaller one,
				// so return NULL on failure.
				if (noMatch != NULL)
					return 0;

				noMatch = eL;
			}
		}
		// Return the constant from the larger set that wasn't in the smaller
		return noMatch;
	}

	// Matches patterns of the form:
	// (a^b^c^d) & (a^b^c^d^e) => (a^b^c^d) & ~e, where e is numeric
	// The terms don't necessarily have to be in the same order; we extract the
	// XOR subterms from both sides and find the missing value from the smaller
	// XOR chain.
	int pat_AndXor(minsn_t *ins, mblock_t * /*blk*/)
	{
		// Instruction must be AND ...
		if (ins->opcode != m_and)
			return 0;

		// ... at least one side must be XOR ...
		bool bLeftIsNotXor  = ins->l.t != mop_d || ins->l.d->opcode == m_xor;
		bool bRightIsNotXor = ins->r.t != mop_d || ins->r.d->opcode == m_xor;
		if (!bLeftIsNotXor && !bRightIsNotXor)
			return 0;

		// Collect the constant and non-constant parts of the XOR chains. We
		// use the XorSimplifier class, but we don't actually simplify the
		// instruction; we just make use of the existing functionality to
		// collect the operands that are XORed together.
		XorSimplifier xsL, xsR;
		xsL.Insert(&ins->l);
		xsR.Insert(&ins->r);

		// There must be the same number of non-constant terms on both sides
		if (xsL.m_NonConst.size() != xsR.m_NonConst.size())
			return 0;

		bool bLeftIsSmaller;
		std::set<mop_t *> *smaller, *bigger;

		// Either the left is one bigger than the right...
		if (xsL.m_Const.size() == xsR.m_Const.size() + 1)
			smaller = &xsR.m_Const, bigger = &xsL.m_Const, bLeftIsSmaller = false;

		// Or the right is one bigger than the left...
		else
		if (xsR.m_Const.size() == xsL.m_Const.size() + 1)
			smaller = &xsL.m_Const, bigger = &xsR.m_Const, bLeftIsSmaller = true;

		// Or, the pattern doesn't match, so return 0.
		else
			return 0;

		// The sets of non-constant operands must match
		if (!(NonConstSetsMatch(&xsL.m_NonConst, &xsR.m_NonConst)))
			return 0;

		// Find the one constant value that wasn't common to both sides
		mop_t *noMatch = FindNonCommonConstant(smaller, bigger);

		// If there wasn't one, the pattern failed, so return 0
		if (noMatch == NULL)
			return 0;

		// Invert the non-common number and truncate it down to its proper size
		noMatch->nnn->update_value(~noMatch->nnn->value & ((1ULL << (noMatch->size * 8)) - 1));

		// Replace the larger XOR construct with the now-inverted value
		if (bLeftIsSmaller)
			ins->r.swap(*noMatch);
		else
			ins->l.swap(*noMatch);

		// msg("[I] pat_AndXor\n");
		return 1;
	}

	// Replaces conditionals of the form !(!c1 || !c2) with (c1 && c2).
	int pat_LnotOrLnotLnot(minsn_t *ins, mblock_t * /*blk*/)
	{
		// The whole expression must be logically negated.
		minsn_t *inner;
		if (!ExtractLogicallyNegatedTerm(ins, inner) || inner == NULL)
			return 0;

		// The thing that was negated must be an OR with compound operands.
		if (inner->opcode != m_or || inner->l.t != mop_d || inner->r.t != mop_d)
			return 0;

		// The two compound operands must also be negated
		minsn_t *insLeft = inner->l.d;
		minsn_t *insRight = inner->r.d;
		mop_t *opLeft, *opRight;
		if (!ExtractLogicallyNegatedTerm(inner->l.d, insLeft, &opLeft) || !ExtractLogicallyNegatedTerm(inner->r.d, insRight, &opRight))
			return 0;

		// If we're here, the pattern matched. Make the AND.
		ins->opcode = m_and;
		ins->l.swap(*opLeft);
		ins->r.swap(*opRight);
		// msg("[I] pat_LnotOrLnotLnot\n");
		return 1;
	}

	// Replaces terms of the form ~(~x | n), where n is a number, with x & ~n.
	int pat_BnotOrBnotConst(minsn_t *ins, mblock_t * /*blk*/)
	{
		// We're looking for BNOT instructions (~y)...
		if (ins->opcode != m_bnot || ins->l.t != mop_d)
			return 0;

		// ... where x is an OR instruction ...
		minsn_t *inner = ins->l.d;
		if (inner->opcode != m_or)
			return 0;

		// ... and one side is constant, where the other one isn't ...
		mop_t *orNum, *orNonNum;
		if (!ExtractNumAndNonNum(inner, orNum, orNonNum))
			return 0;

		// ... and the non-constant part is itself a BNOT instruction (~x)
		if (orNonNum->t != mop_d || orNonNum->d->opcode != m_bnot)
			return 0;

		// Once we found it, rewrite the top-level BNOT with an AND
		ins->opcode = m_and;
		ins->l.swap(orNonNum->d->l);

		// Invert the numeric part
		uint64 notNum = ~(orNum->nnn->value) & ((1ULL << (orNum->size * 8)) - 1);
		ins->r.make_number(notNum, orNum->size);

		return 1;
	}

	// This function just inspects the instruction and calls the
	// pattern-replacement functions above to perform deobfuscation.
	int Optimize(minsn_t *ins, mblock_t *blk)
	{
		int iLocalRetVal = 0;

		switch (ins->opcode)
		{
		default:
			break;
		case m_bnot:
			iLocalRetVal = pat_BnotOrBnotConst(ins, blk);
			break;
		case m_or:
			iLocalRetVal = pat_OrAndNot(ins, blk);
			if (!iLocalRetVal)
				iLocalRetVal = pat_OrViaXorAnd(ins, blk);
			if (!iLocalRetVal)
				iLocalRetVal = pat_OrNegatedSameCondition(ins, blk);
			if (!iLocalRetVal)
				iLocalRetVal = pat_LogicAnd1(ins, blk);
			if (!iLocalRetVal)
				iLocalRetVal = pat_MulSub2(ins, blk); // added
			break;
		case m_and:
			iLocalRetVal = pat_AndXor(ins, blk);
			if (!iLocalRetVal)
				iLocalRetVal = pat_MulSub(ins, blk);
			break;
		case m_xor:
			iLocalRetVal = pat_XorChain(ins, blk);
			if(!iLocalRetVal)
				iLocalRetVal = pat_LnotOrLnotLnot(ins, blk);
			if (!iLocalRetVal)
				iLocalRetVal = pat_LogicAnd1(ins, blk);
			break;
		case m_lnot:
			iLocalRetVal = pat_LnotOrLnotLnot(ins, blk);
			break;
		case m_setl:
		case m_jl:
		case m_jge:
		case m_seto: // cause INTERR 50862 -> replace in later maturity level
			iLocalRetVal = pat_InitedVarCondImm(ins, blk); // added
			break;
		case m_sets:
			iLocalRetVal = pat_InitedVarSubImmCond0(ins, blk); // added
			break;
		case m_mov:
			//iLocalRetVal = pat_InitedVarMov(ins); data-flow tracking required
			break;
		///*
		case m_jnz: // to optimize setl sub-instruction (jnz > xor > setl)
			struct Blah2 : minsn_visitor_t
			{
				int idaapi visit_minsn()
				{
					if (curins->opcode == m_setl)
					{
						if (curins->l.t != mop_r || curins->r.t != mop_n)
							return 0;
						mop_t op_r = curins->l; // curins->d is mop_z(0)
						int ret = othis->pat_InitedVarCondImm(curins, mb);
						// IDA automatically optimizes setl (0 < #0xA) => nop
						// nop is not propagatable because it does not generate any value (INTERR 50800)
						// replace nop with e.g., mov 1, cl
						if (ret && curins->opcode == m_nop)
						{
							curins->opcode = m_mov;
							curins->l.make_number(1, 1);
							curins->d.make_reg(op_r.r, 1);
							if (mb)
								mb->optimize_insn(curins);
							else
								curins->optimize_solo();
						}
						return ret;
					}
					return 0;
				}
				ObfCompilerOptimizer *othis;
				mblock_t *mb;
				Blah2(ObfCompilerOptimizer *o, mblock_t *b) : othis(o), mb(b) { };
			};
			Blah2 b2(this, blk);
			iLocalRetVal += ins->for_all_insns(b2);
		//*/
		}
		return iLocalRetVal;
	}

	// This is the virtual function dictated by the optinsn_t interface. This
	// function gets called by the Hex-Rays kernel; we optimize the microcode.
	int func(mblock_t *blk, minsn_t *ins);
};

// Callback function. Do pattern-deobfuscation.
int ObfCompilerOptimizer::func(mblock_t *blk, minsn_t *ins)
{
#if OPTVERBOSE
	char buf[1000];
	mcode_t_to_string(ins, buf, sizeof(buf));
	msg("ObfCompilerOptimizer: %a %s\n", ins->ea, buf);
#endif

	int retVal = Optimize(ins, blk);
	int iLocalRetVal = 0;

	// This callback doesn't seem to get called for subinstructions of
	// conditional branches. So, if we're dealing with a conditional branch,
	// manually optimize the condition expression
	if ((is_mcode_jcond(ins->opcode) || is_mcode_set(ins->opcode)) && ins->l.t == mop_d)
	{
		// In order to optimize the jcc condition, we actually need a different
		// structure than optinsn_t: in particular, we need a minsn_visitor_t.
		// This local structure declaration just passes the calls to
		// minsn_visitor_t::visit_minsn onto the Optimize function in this
		// optinsn_t object.
		struct Blah : minsn_visitor_t
		{
			int idaapi visit_minsn()
			{
				return othis->Optimize(this->curins, blk);
			}
			ObfCompilerOptimizer *othis;
			Blah(ObfCompilerOptimizer *o) : othis(o) { };
		};

		Blah b(this);

		// Optimize all subinstructions of the JCC conditional
		iLocalRetVal += ins->for_all_insns(b);
		// For good measure, optimize the top-level instruction again. I don't
		// know if this is necessary or important, but whatever.
		// iLocalRetVal += Optimize(ins);
	}
	retVal += iLocalRetVal;

	// If any optimizations were performed...
	if (retVal)
	{
#if OPTVERBOSE
		// ... inform the user ...
		mcode_t_to_string(ins, buf, sizeof(buf));
		msg("ObfCompilerOptimizer: replaced by %s\n", buf);
#endif
#if IDA_SDK_VERSION == 710
		ins->optimize_flat();
#elif IDA_SDK_VERSION >= 720
		if (blk)
			blk->optimize_insn(ins);
		else
			ins->optimize_solo();
#endif
		// I got an INTERR if I optimized jcc conditionals without marking the lists dirty.
		blk->mark_lists_dirty();
		blk->mba->verify(true);
		//blk->mba->optimize_local(0);
		// ... verify we haven't corrupted anything
		//blk->mba->verify(true);
	}
	return retVal;
}