machine-code-analyzer.py

#!/usr/bin/env python3
#
# Email: Hagen Paul Pfeifer <hagen@jauu.net>

# Machine-Code-Analyzer is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation, either version 3 of
# the License, or (at your option) any later version.
#
# MachineCodeAnalyzer is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with MachineCodeAnalyzer. If not, see <http://www.gnu.org/licenses/>.


import sys
import os
import argparse
import array
import json
import re
import math
import shutil
import subprocess
import textwrap
import time

try:
    import capstone
except ImportError:
    sys.stderr.write("Capstone is not installed! Install via pip install capstone\n")
    sys.exit(1)

try:
    from elftools.elf.elffile import ELFFile
    from elftools.elf.constants import SH_FLAGS
except ImportError:
    sys.stderr.write("Pyelftools is not installed! Install via pip install pyelftools\n")
    sys.exit(1)

# Optional package, only required for graph generation (-g)
try:
    import matplotlib
    matplotlib.use('Agg')
    import matplotlib.pyplot as plt
    import matplotlib.colors
    import matplotlib.patches
except ImportError:
    plt = None


__programm__ = "machine-code-analyzer"
__author__   = "Hagen Paul Pfeifer"
__version__  = "1"
__license__  = "GPLv3"

# custom exceptions
class ArgumentException(Exception): pass
class InternalSequenceException(Exception): pass
class InternalException(Exception): pass
class SequenceContainerException(InternalException): pass
class NotImplementedException(InternalException): pass
class SkipProcessStepException(Exception): pass
class UnitException(Exception): pass


GRAPH_DESCRIPTIONS = {
    'function-sizes': ("""The largest functions of the binary, ranked by machine code size.

Each bar is one function, the length is its size in byte as recorded in the
ELF symbol table, the percentage is its share of the whole analyzed code.
Large functions are the first candidates for a closer look: heavy inlining,
huge switch statements or generated code show up here immediately.""",
    "Function size in byte",
    "Function names, largest on top"),

    'function-histogram': ("""How the function sizes are distributed, in power of two buckets.

Each bar counts the functions whose size falls into the bucket, "<= 64"
collects everything from 33 to 64 byte. Most code bases peak in the low
hundreds of bytes. A fat tail of huge functions or a spike of tiny wrapper
functions is worth investigating.""",
    "Function size bucket in byte, power of two upper bound",
    "Number of functions in the bucket"),

    'function-cumulative': ("""How much of the total code is covered by the largest functions.

Functions are sorted by size, largest first, and summed up along the x axis.
The marked points show where 50 and 90 percent of the code is reached: "50%
of the code in 5% of the functions" means half the binary lives in a handful
of big functions. Useful to judge how top heavy a code base is and where
size optimizations would pay off.""",
    "Share of functions in percent, sorted by size, largest first",
    "Cumulative share of the total code size in percent"),

    'function-alignment': ("""On which address boundaries the functions start.

Each bar counts the functions whose start address is divisible by the given
alignment. Compilers usually align function entries to 16 or 32 byte for
fetch efficiency, so the small alignments should be rare. A large
"Unaligned" share hints at handwritten assembly or unusual build flags.""",
    "Number of functions",
    "Start address alignment in byte"),

    'instruction-categories': ("""Which instruction categories dominate the binary.

Every decoded instruction is classified (data transfer, control transfer,
arithmetic, SSE, ...) and counted. Typical compiler output is dominated by
data and control transfer. A visible SIMD share reveals vectorized code,
fat arithmetic buckets point to computation heavy loops.""",
    "Number of instructions",
    "Instruction category"),

    'instruction-mnemonics': ("""The most frequent instruction mnemonics.

Counts per mnemonic in AT&T syntax including the size suffix, the
percentage relates to all instructions of the binary. The mov family leads
in almost every binary, the interesting information is what follows it:
many call/ret pairs mean small functions, many conditional jumps mean
branchy code.""",
    "Number of instructions",
    "Mnemonic in AT&T syntax, most frequent on top"),

    'instruction-lengths': ("""How long the instruction encodings are.

x86 instructions are variable length, one to fifteen byte. The distribution
shows the encoding density of the binary: many short instructions mean
compact code that fits well into the instruction cache, long encodings come
from SIMD prefixes, large immediates and complex addressing.""",
    "Instruction length in byte",
    "Number of instructions with this length"),

    'instruction-ranges': ("""How much the encoding length varies per mnemonic.

The dot marks the average encoding length of the mnemonic, the line spans
from the shortest to the longest encoding observed in the binary. Wide
spans (mov, cmp) come from the many operand forms - register, immediate,
memory with small or large offsets. Mnemonics without a span (ret) always
encode to the same size.""",
    "Encoding length in byte, dot = average, line = min to max",
    "Mnemonic in AT&T syntax, most frequent on top"),

    'branch-histogram': ("""How far local jumps go, split into forward and backward.

The distance is measured in byte from the jump instruction to its target
inside the same function, bucketed by powers of two. Forward jumps skip
code (if/else, error checks), backward jumps close loops. Long distances
usually come from very large functions, interpreter loops and big switch
dispatchers show up as a far tail.""",
    "Jump distance bucket in byte, power of two upper bound",
    "Number of jumps in the bucket"),

    'branch-direction': ("""The share of jump directions and jump conditions.

Two proportion bars over all local jumps. Forward jumps dominate in most
compiler output because error checks jump forward past the hot path. The
conditional share shows how much of the local control flow actually depends
on data at runtime.""",
    "Share of all local jumps, one 100 percent bar per row",
    "Two rows: jump direction and jump condition"),

    'branch-percentiles': ("""Percentile curves of the local jump distances.

Read it like a latency plot: each curve shows the share of jumps that stay
within x byte. p50 is the median jump distance, p99 catches the outliers.
Backward (loop) jumps are systematically longer than forward jumps in most
binaries; the log axis shows both the short skips and the huge outliers.""",
    "Jump distance in byte, log scale",
    "Share of jumps within this distance in percent"),

    'stack-histogram': ("""How much stack the functions allocate, in power of two buckets.

Counts functions per static stack allocation bucket. Most functions get by
with well below 128 byte. The 4096 byte bucket is typically filled by
PATH_MAX sized buffers.""",
    "Static stack allocation bucket in byte, power of two",
    "Number of functions in the bucket"),

    'stack-allocation': ("""The share of functions that allocate stack at all.

Functions with a static or dynamic stack frame versus functions that run
entirely in registers (leaf functions, small helpers). A high allocation
share is normal for unoptimized builds, optimized code keeps many small
functions frameless.""",
    "Share of all functions, one 100 percent bar",
    "Single row: functions with versus without stack allocation"),

    'stack-sizes': ("""Which exact static allocation sizes occur and how often.

Largest allocation sizes first, each bar counts the functions that allocate
exactly this amount. Repeated identical sizes usually come from the same
buffer pattern, dozens of functions with exactly 4096 byte point to
PATH_MAX arrays on the stack.""",
    "Number of functions with exactly this allocation size",
    "Static allocation size in byte, largest on top"),

    'atomic-operations': ("""The mix of atomic operations, fences and spin wait hints.

Locked read-modify-write instructions split into compare-and-swap,
fetch-and-add, atomic swap and the rest, plus memory fences and pause
hints. The profile reveals the synchronization style: CAS heavy code
implements lock free structures, plain locked RMW dominates in reference
counting, many pause hints mean spin waiting.""",
    "Number of operations",
    "Operation class"),

    'atomic-functions': ("""The functions with the most atomic operations and fences.

The synchronization hot spots of the binary. Functions that concentrate
many atomics are the places where locking strategy, cache line contention
and memory ordering deserve a review.""",
    "Number of atomic operations and fences",
    "Function names, most atomics on top"),

    'layout-map': ("""Where each function switches from hot to cold code.

The largest functions as normalized strips: the orange head is the linear
path from the function entry to the first ret, the purple tail is code the
compiler moved out of the hot path - error handling, unlikely branches,
cleanup. The ticks mark conditional jumps into the tail. A tiny head with a
huge tail means either a very early return or a lot of outlined error
handling.""",
    "Relative position within the function, 0 to 100 percent",
    "Function names, largest on top"),

    'layout-split': ("""How the code splits into hot and cold overall.

Three proportion bars: hot versus cold bytes over the whole binary, how
many functions have a cold tail at all, and how many functions keep a
frame pointer (push %rbp; mov %rsp,%rbp prologue) versus frame pointer
omission. The cold share is code the compiler considered unlikely to
run - a rough measure of how much error handling the binary carries.""",
    "Share, one 100 percent bar per row",
    "Three rows: code bytes, cold tail functions, frame pointer"),

    'layout-histogram': ("""How large the cold tails are relative to their functions.

Buckets of the cold tail share: "70-80%" counts functions where most bytes
sit behind the first ret. The left edge holds the functions that are
essentially all hot path, the right edge functions that are mostly error
handling.""",
    "Cold tail share bucket in percent of the function size",
    "Number of functions in the bucket"),

    'layout-scatter': ("""Function size versus cold tail share, one dot per function.

The x axis is logarithmic. The usual pattern: small functions have no cold
tail at all (the row at 0%), and the bigger a function gets the larger the
share of code the compiler moves out of its hot path.""",
    "Function size in byte, log scale",
    "Cold tail share in percent, one dot per function"),

    'diff-changes': ("""Which functions grew or shrank between the two binaries.

Diverging bars, growth to the right in warm, shrinkage to the left in
teal, including functions that only exist in one of the binaries. Sorted
by the size of the change. Useful to see what a compiler flag or a patch
really did to the generated code.""",
    "Code size delta in byte, negative means shrunk",
    "Function names, largest change on top"),

    'diff-categories': ("""How the instruction mix shifted between the two binaries.

Per category delta of the instruction counts. A drop in control transfer
with stable arithmetic usually means better branch elimination, a jump in
SIMD categories means the vectorizer kicked in.""",
    "Instruction count delta, negative means fewer",
    "Instruction category"),

    'idiom-pairs': ("""The most frequent instruction pairs.

Counts how often one instruction directly follows another inside the
same function, mnemonics normalized without their size suffixes. The
top pairs are the compiler's idioms: cmp -> je is a comparison branch,
test -> je a null or flag check, xor -> ret returns zero. The pair
profile is a fingerprint of the code generator.""",
    "Number of occurrences",
    "Instruction pair, most frequent on top"),

    'idiom-matrix': ("""Which instruction follows which, as a transition matrix.

Rows are the current instruction, columns the following one. A cell
shows how often the column instruction comes next, in percent of all
successors of the row instruction. Bright cells are strong couples:
after a cmp almost always follows a conditional jump. Only the most
frequent mnemonics are shown.""",
    "Next instruction",
    "Current instruction"),

    'idiom-flow': ("""What each instruction is followed by, one bar per instruction.

For the most frequent instructions, the bar is split into the instructions
that follow it, widest share first and labelled inline. Reads left to right
as "after this instruction, this is what comes next": after a cmp almost
always a conditional jump, after a push another push. A simpler, more
tangible view of the same data as the transition matrix.""",
    "Share of the next instruction in percent",
    "Current instruction, most frequent on top"),

    'idiom-trigrams': ("""The most frequent instruction triples.

Like the pairs, one step longer: three instructions in a row. Triples
expose larger building blocks, the function epilogue pop -> pop -> ret,
argument setup before calls or unrolled copy sequences.""",
    "Number of occurrences",
    "Instruction triple, most frequent on top"),

    'call-called': ("""The most called functions.

Counts the direct call sites that target each function (fan-in). The
top entries are the work horses of the binary: allocation, locking,
error and string handling. Calls that leave the binary through the PLT
are summed into one external entry in the text report.""",
    "Number of call sites targeting the function",
    "Function names, most called on top"),

    'call-fanout': ("""How many calls the functions make.

Buckets of call sites per function (fan-out). The zero bucket holds the
leaf functions that call nothing at all - the more of them, the flatter
the call graph. Functions with dozens of call sites are coordinators
that mostly orchestrate other code.""",
    "Call sites per function, bucketed",
    "Number of functions in the bucket"),

    'call-kinds': ("""The mix of call kinds and the leaf share.

Direct internal calls stay inside the binary, external calls leave
through the PLT into shared libraries, indirect calls go through a
register or memory pointer - function pointers and vtables. A high
indirect share makes static analysis and branch prediction harder. The
second row shows how many functions are leaves.""",
    "Share, one 100 percent bar per row",
    "Two rows: call kinds and leaf functions"),

    'hardening-card': ("""The full mitigation status of the binary, one row
per layer of defense.

PIE/ASLR, NX, RELRO, the stack canary, CET/IBT and FORTIFY, read from
the ELF headers and the instruction stream. Green means the mitigation
is on, amber means partial (partial RELRO, incomplete CET, no FORTIFY),
red means off. It is the checksec view of a single binary, at a
glance.""",
    "Mitigation status (green on, amber partial, red off)",
    "One row per mitigation layer"),

    'hardening-coverage': ("""How much of the binary is covered by mitigations.

CET/IBT: functions starting with endbr64, a jump target barrier
against ROP/JOP attacks - near 100% means the binary was built with
-fcf-protection. Stack protector: functions that load the canary from
%fs:0x28; only functions with buffers get a canary under
-fstack-protector-strong, so well below 100% is normal there.""",
    "Share of functions",
    "One row per mitigation"),

    'hardening-unprotected': ("""The largest functions without a stack canary.

Big functions without a canary load either have no stack buffers at
all (fine) or were compiled without stack protection (worth a look).
Function size is a rough proxy for attack surface, review from the
top.""",
    "Function size in byte",
    "Function names, largest on top"),

    'register-usage': ("""How often each general purpose register is used.

Counts every register mention in the operands, sub-registers (eax, ax,
al) folded into their family (rax). The classic picture: rax dominates
as return and scratch register, then the argument registers rdi, rsi,
rdx, rcx. The drop towards r8-r15 shows how much the compiler avoids
the REX prefixed upper half.""",
    "Register mentions in operands",
    "Register family, architectural order"),

    'register-classes': ("""Register class shares.

Caller-saved registers are free scratch, callee-saved ones must be
preserved across calls - heavy callee-saved use means functions with a
lot of live state. The second row shows how many mentions need a REX
prefix (r8-r15), the third the SIMD register share.""",
    "Share of register mentions, one 100 percent bar per row",
    "Three rows: save class, REX need, GP versus SIMD"),

    'register-addressing': ("""Which operand forms the instructions use.

Register operands are the fastest, immediates encode constants inline,
memory operands go through the cache hierarchy. RIP-relative addressing
is the position independent way to reach globals, SIB forms
(base + index * scale) are typically array accesses.""",
    "Number of operands",
    "Operand form"),
}


def module_parser(module, description=None, no_exclude=True):
    parser = argparse.ArgumentParser(
            prog="%s %s" % (os.path.basename(sys.argv[0]), module),
            description=description,
            formatter_class=argparse.RawDescriptionHelpFormatter)
    parser.add_argument('-v', '--verbose', dest='verbose', action='store_true',
            help='show verbose messages')
    parser.add_argument('--json-out', dest='json_out', metavar='FILE',
            default=None,
            help='write the analysis results as JSON to FILE, '
                 'parent directories are created')
    if no_exclude:
        parser.add_argument('-x', '--no-exclude', dest='no_exclude',
                action='store_true',
                help='do *not* exclude glibc/gcc runtime helper functions '
                     'like _start or __do_global_dtors_aux')
    return parser


def add_graph_arguments(parser, graphs):
    # graphs: list of (name, default filename, help text)
    parser.add_argument('-g', '--graphs', dest='graphs_all', action='store_true',
            help='generate all module graphs')
    parser.add_argument('--graph-style', dest='graph_style',
            choices=('light', 'dark'), default='light',
            help='color style of the graphs, e.g. for dark slides (default: light)')
    parser.add_argument('--graph-transparent', dest='graph_transparent',
            action='store_true',
            help='render with a transparent background, e.g. to embed on a '
                 'web page (pair with --graph-style dark for a dark page)')
    lines = ["available graphs:"]
    for name, default_filename, helptext in graphs:
        parser.add_argument('--graph-%s' % (name), action='store_true',
                help='generate the %s graph' % (helptext))
        parser.add_argument('--graph-%s-filename' % (name), metavar='FILE',
                default=None,
                help='PNG output file, implies --graph-%s (default: %s)' %
                     (name, default_filename))
        summary = helptext
        key = default_filename[:-len('.png')]
        if key in GRAPH_DESCRIPTIONS:
            summary = GRAPH_DESCRIPTIONS[key][0].strip().split('\n')[0]
        lines.append("  --graph-%-12s %s" % (name, summary))
    lines.append("")
    lines.append("every graph is written as PNG at 300 dpi together with a")
    lines.append("<name>.png.txt sidecar explaining the picture and its axes")
    parser.epilog = '\n'.join(lines)


def finish_graph_arguments(opts, graphs):
    # a given filename implies the graph option itself, -g selects all
    requested = False
    for name, default_filename, helptext in graphs:
        attr = 'graph_%s' % (name)
        filename_attr = '%s_filename' % (attr)
        if getattr(opts, filename_attr):
            setattr(opts, attr, True)
        elif opts.graphs_all:
            setattr(opts, attr, True)
        if not getattr(opts, filename_attr):
            setattr(opts, filename_attr, default_filename)
        requested = requested or getattr(opts, attr)
    if requested and not plt:
        sys.stderr.write("Want graphs but no matplotlib given!\n")
        sys.exit(1)


class FunctionExcluder:

    def __init__(self):
        self.exclude_files = ['_start', '_fini', '__libc_csu_fini',
                              '__do_global_dtors_aux', '__libc_csu_init',
                              'register_tm_clones', 'frame_dummy',
                              '__init', 'deregister_tm_clones', '_init']

    def is_excluded(self, function_name):
        if function_name.endswith("@plt"):
            return True
        if function_name.endswith("@plt-0x10"):
            return True
        if function_name in self.exclude_files:
            return True
        return False


class RetObj:

    STATIC = 0
    DYNAMIC = 1
    NO_STACK = 2

    def __init__(self, stack_type):
        self.stack_type = stack_type
        self.register = None


class InstructionCategory:
    UNKNOWN = 0

    # E.g. http://flint.cs.yale.edu/cs422/doc/24547012.pdf
    BINARY_ARITHMETIC = 32
    DECIMAL_ARITHMETIC = 33
    LOGICAL = 34
    SHIFT_ROTATE = 35
    BIT_BYTE = 36
    CONTROL_TRANSFER = 37
    STRING = 38
    FLAG_CONTROL = 39
    SEGMENT_REGISTER = 40
    MISC = 41
    DATA_TRANSFER =  42
    FLOATING_POINT = 43
    SYSTEM = 44

    SIMD = 9
    MMX = 10
    SSE = 11
    E3DN = 12
    SSE2 = 13
    SSE3 = 14
    SSSE3 = 15
    SSE41 = 16
    SSE42 = 17
    SSE4A = 18
    AES = 19
    AVX = 20
    FMA = 21
    FMA4 = 22
    CPUID = 23
    MMXEXT = 24

    # external lookup table, filled from the JSON database
    lookup_table = dict()

    @staticmethod
    def _cat_from_string(name):
        # map JSON category names to the existing enum
        mapping = {
            "UNKNOWN": InstructionCategory.UNKNOWN,
            "DATA_TRANSFER": InstructionCategory.DATA_TRANSFER,
            "BINARY_ARITHMETIC": InstructionCategory.BINARY_ARITHMETIC,
            "DECIMAL_ARITHMETIC": InstructionCategory.DECIMAL_ARITHMETIC,
            "LOGICAL": InstructionCategory.LOGICAL,
            "SHIFT_ROTATE": InstructionCategory.SHIFT_ROTATE,
            "BIT_BYTE": InstructionCategory.BIT_BYTE,
            "CONTROL_TRANSFER": InstructionCategory.CONTROL_TRANSFER,
            "STRING": InstructionCategory.STRING,
            "FLAG_CONTROL": InstructionCategory.FLAG_CONTROL,
            "SEGMENT_REGISTER": InstructionCategory.SEGMENT_REGISTER,
            "MISC": InstructionCategory.MISC,
            "FLOATING_POINT": InstructionCategory.FLOATING_POINT,
            "SYSTEM": InstructionCategory.SYSTEM,

            # instruction family mapping
            "SIMD": InstructionCategory.SIMD,
            "MMX": InstructionCategory.MMX,
            "MMXEXT": InstructionCategory.MMXEXT,
            "SSE": InstructionCategory.SSE,
            "E3DN": InstructionCategory.E3DN,
            "SSE2": InstructionCategory.SSE2,
            "SSE3": InstructionCategory.SSE3,
            "SSSE3": InstructionCategory.SSSE3,
            "SSE41": InstructionCategory.SSE41,
            "SSE42": InstructionCategory.SSE42,
            "SSE4A": InstructionCategory.SSE4A,
            "AES": InstructionCategory.AES,
            "PCLMULQDQ": InstructionCategory.AES,   # crypto related
            "AVX": InstructionCategory.AVX,
            "AVX2": InstructionCategory.AVX,
            "AVX512": InstructionCategory.AVX,
            "FMA": InstructionCategory.FMA,
            "FMA4": InstructionCategory.FMA4,
            "BMI1": InstructionCategory.LOGICAL,
            "BMI2": InstructionCategory.LOGICAL,
            "SHA": InstructionCategory.AES,
            "GFNI": InstructionCategory.LOGICAL,
            "AMX": InstructionCategory.AVX,
            "CPUID": InstructionCategory.CPUID
        }
        return mapping.get(name, InstructionCategory.UNKNOWN)

    @staticmethod
    def init_instruction_table(db_path=None):
        """
        Load the mnemonic database from JSON. If the database is
        missing or broken the lookup table stays empty and the
        heuristic guesser handles all mnemonics.
        """
        InstructionCategory.lookup_table.clear()

        if db_path is not None:
            path = db_path
        else:
            base = os.path.dirname(os.path.abspath(__file__))
            path = os.path.join(base, "data", "instruction-db.json")

        try:
            with open(path, "r", encoding="utf-8") as f:
                doc = json.load(f)
        except FileNotFoundError:
            sys.stderr.write("No instruction database (%s), "
                             "falling back to heuristics\n" % (path))
            return
        except (ValueError, OSError) as e:
            sys.stderr.write("Broken instruction database %s: %s, "
                             "falling back to heuristics\n" % (path, e))
            return

        cats = doc.get("categories", {})
        for cat_name, mnems in cats.items():
            cat_enum = InstructionCategory._cat_from_string(cat_name)
            for m in mnems:
                m_lower = m.strip().lower()
                if not m_lower:
                    continue
                InstructionCategory.lookup_table[m_lower] = [cat_enum, None]

    @staticmethod
    def _heuristic_guess(k):
        # simple suffix/prefix based classification
        def anyprefix(s, ps): return any(s.startswith(p) for p in ps)
        base = re.sub(r'(b|w|l|q)$', '', k)  # strip size suffix (addl -> add)

        # control flow
        if k in ("call","ret","jmp") or k.startswith("j"):
            return InstructionCategory.CONTROL_TRANSFER
        if k in ("endbr","endbr64","endbr32","notrack"):
            return InstructionCategory.CONTROL_TRANSFER

        # conditional moves / sets
        if base.startswith("cmov"):
            return InstructionCategory.DATA_TRANSFER
        if base.startswith("set"):
            return InstructionCategory.BIT_BYTE

        # data movement
        if base.startswith("mov") or base in ("xchg","bswap","lea","push","pop"):
            return InstructionCategory.DATA_TRANSFER

        # logic and tests
        if base in ("and","or","xor","not","bt","bts","btr","btc","bsr","tzcnt","lzcnt"):
            return InstructionCategory.LOGICAL
        if base == "test":
            return InstructionCategory.BIT_BYTE

        # arithmetic
        if anyprefix(base, ("add","sub","adc","sbb","mul","imul","div","idiv","inc","dec","neg","cmp")):
            return InstructionCategory.BINARY_ARITHMETIC

        # shift/rotate
        if anyprefix(base, ("shl","sal","shr","sar","rol","ror","rcl","rcr","shld","shrd")):
            return InstructionCategory.SHIFT_ROTATE

        # typical SSE/SSE2 mnemonics
        if anyprefix(k, ("addps","subps","mulps","divps","movaps","movups","shufps","movss","cvtss2sd")):
            return InstructionCategory.SSE
        if anyprefix(k, (
            "addpd","subpd","mulpd","divpd","addsd","subsd","mulsd","divsd",
            "ucomisd","comisd","shufpd","movapd","movupd","movsd","xorpd","orpd","andnpd",
            "cvtsi2sd","cvttsd2si","cvtdq2pd","pshufd","psrldq","unpcklpd"
        )):
            return InstructionCategory.SSE2

        # MMX/packed
        if anyprefix(k, ("pcmpeq","pcmpgt","padd","psub","psll","psrl","psra","punpck","pmov","por","pand","pxor","pack")):
            return InstructionCategory.MMX

        # classic x87 FPU
        if anyprefix(k, ("fld","fst","fstp","fnstsw","fadd","fsub","fmul","fdiv","fprem","fchs","fabs","fsqrt")):
            return InstructionCategory.FLOATING_POINT

        # system/misc
        if k in ("ud2","hlt","nop","nopl","nopw"):
            return InstructionCategory.MISC

        return InstructionCategory.UNKNOWN

    @staticmethod
    def guess(instructon):
        # capstone encodes prefixes into the mnemonic ("lock addl",
        # "notrack jmpq"), the instruction itself is the last token
        k = instructon.lower().split()[-1]
        if k in InstructionCategory.lookup_table:
            return InstructionCategory.lookup_table[k][0]
        # retry with AT&T size suffixes stripped (fildll -> fild)
        base = re.sub(r'[bwlq]+$', '', k)
        if base in InstructionCategory.lookup_table:
            return InstructionCategory.lookup_table[base][0]
        return InstructionCategory._heuristic_guess(k)

    @staticmethod
    def str(cat):
        if cat == InstructionCategory.UNKNOWN: return "unknown"

        if cat == InstructionCategory.DATA_TRANSFER: return "DATA_TRANSFER"
        if cat == InstructionCategory.BINARY_ARITHMETIC: return "BINARY_ARITHMETIC"
        if cat == InstructionCategory.DECIMAL_ARITHMETIC: return "DECIMAL_ARITHMETIC"
        if cat == InstructionCategory.LOGICAL: return "LOGICAL"
        if cat == InstructionCategory.SHIFT_ROTATE: return "SHIFT_ROTATE"
        if cat == InstructionCategory.BIT_BYTE: return "BIT_BYTE"
        if cat == InstructionCategory.CONTROL_TRANSFER: return "CONTROL_TRANSFER"
        if cat == InstructionCategory.STRING: return "STRING"
        if cat == InstructionCategory.FLAG_CONTROL: return "FLAG_CONTROL"
        if cat == InstructionCategory.SEGMENT_REGISTER: return "SEGMENT_REGISTER"
        if cat == InstructionCategory.MISC: return "MISC"
        if cat == InstructionCategory.FLOATING_POINT: return "FLOATING_POINT"
        if cat == InstructionCategory.SYSTEM: return "SYSTEM"

        if cat == InstructionCategory.SIMD: return "SIMD"
        if cat == InstructionCategory.MMX: return "MMX"
        if cat == InstructionCategory.SSE: return "SSE"
        if cat == InstructionCategory.E3DN: return "E3DN"
        if cat == InstructionCategory.SSE2: return "SSE2"
        if cat == InstructionCategory.SSE3: return "SSE3"
        if cat == InstructionCategory.SSSE3: return "SSSE3"
        if cat == InstructionCategory.SSE41: return "SSE41"
        if cat == InstructionCategory.SSE42: return "SSE42"
        if cat == InstructionCategory.SSE4A: return "SSE4A"
        if cat == InstructionCategory.AES: return "AES"
        if cat == InstructionCategory.AVX: return "AVX"
        if cat == InstructionCategory.FMA: return "FMA"
        if cat == InstructionCategory.FMA4: return "FMA4"
        if cat == InstructionCategory.CPUID: return "CPUID"
        if cat == InstructionCategory.MMXEXT: return "MMXEXT"
        raise Exception("Programmed error - no string repr defined")



class Context:

    def __init__(self):
        self.function_name = None
        self.function_start_address  = None
        self.function_size = None
        self.section_name  = None



class BinaryAtom:

    TYPE_1 = 1
    TYPE_2 = 2
    TYPE_3 = 3
    TYPE_4 = 4
    TYPE_5 = 5
    TYPE_6 = 6


    def __init__(self, b_type, line, addr, opcode, kwargs):
        self.line       = line
        self.addr       = addr
        self.opcode_str = opcode
        self.opcode_len = len(opcode.replace(" ", "")) // 2
        self.type  = b_type
        self.category   = InstructionCategory.UNKNOWN

        self.src = self.dst = self.jmp_addr = self.jmp_sym = None
        self.is_jump = False
        self.mnemonic = kwargs['mnemonic']

        if b_type == BinaryAtom.TYPE_1:
            self.src = kwargs['src']
            self.dst = kwargs['dst']
            self.jmp_addr = kwargs['jmp-addr']
            self.jmp_sym  = kwargs['jmp-sym']
        elif b_type == BinaryAtom.TYPE_2:
            self.src = kwargs['src']
            self.dst = kwargs['dst']
        elif b_type == BinaryAtom.TYPE_3:
            self.src = kwargs['src']
            self.jmp_addr = kwargs['jmp-addr']
            self.jmp_sym  = kwargs['jmp-sym']
        elif b_type == BinaryAtom.TYPE_4:
            self.src = kwargs['src']
            self.jmp_addr = kwargs['jmp-addr']
        elif b_type == BinaryAtom.TYPE_5:
            self.src = kwargs['src']
        elif b_type == BinaryAtom.TYPE_6:
            pass
        else:
            raise Exception("unknown code")


    def print(self):
        sys.stderr.write("%s\n" % (self.line))
        sys.stderr.write("MNEMONIC: %s  SRC:%s  DST:%s [OPCODE: %s,  LEN:%d]\n" %
            (self.mnemonic, self.src, self.dst,  self.opcode_str, self.opcode_len)) 



class Common:

    def err(self, msg):
        sys.stderr.write(msg)


    def verbose(self, msg):
        if not self.opts.verbose:
            return
        sys.stderr.write(msg)


    def msg(self, msg):
        return sys.stdout.write(msg) - 1


    def line(self, length, char='-'):
        sys.stdout.write(char * length + "\n")



    def msg_underline(self, msg, pre_news=0, post_news=0):
        str_len = len(msg)
        if pre_news:
            self.msg("\n" * pre_news)
        self.msg(msg)
        self.msg("\n" + '=' * str_len)
        if post_news:
            self.msg("\n" * post_news)

    def debug(self, msg):
        # remove next line for debuging purpose
        return
        sys.stderr.write(msg)


    def next_power_of_two(self, n):
        return int(math.pow(2, math.ceil(math.log(n, 2))))


    # graph styles: no chart junk, muted modern palette, one for light
    # and one for dark slides
    GRAPH_STYLES = {
        'light': {
            'bg':        '#ffffff',
            'ink':       '#30343b',
            'frame':     '#565b63',
            'grid':      '#d5d8dc',
            'primary':   '#8b0aa5',
            'secondary': '#f89441',
            'good':      '#3f9b8c',
            'bad':       '#c65f5f',
            'ramp':      (0.03, 0.82),
        },
        'dark': {
            'bg':        '#15171c',
            'ink':       '#d7dae0',
            'frame':     '#8f95a0',
            'grid':      '#3a3e46',
            'primary':   '#c65ddb',
            'secondary': '#f9a860',
            'good':      '#63bfae',
            'bad':       '#e08585',
            'ramp':      (0.22, 0.94),
        },
    }

    def graph_style(self):
        return Common.GRAPH_STYLES[self.opts.graph_style]


    def graph_axes(self, xlabel=None, ylabel=None, figsize=(8.0, 4.5)):
        style = self.graph_style()
        fig, ax = plt.subplots(figsize=figsize, layout='constrained')
        fig.patch.set_facecolor(style['bg'])
        ax.set_facecolor(style['bg'])
        ax.spines['top'].set_visible(False)
        ax.spines['right'].set_visible(False)
        ax.spines['left'].set_color(style['frame'])
        ax.spines['bottom'].set_color(style['frame'])
        ax.tick_params(colors=style['frame'], labelcolor=style['ink'],
                       labelsize=8)
        if xlabel:
            ax.set_xlabel(xlabel, color=style['ink'], fontsize=9)
        if ylabel:
            ax.set_ylabel(ylabel, color=style['ink'], fontsize=9)
        return fig, ax


    def graph_blend(self, color, other, fraction):
        a = matplotlib.colors.to_rgb(color)
        b = matplotlib.colors.to_rgb(other)
        return tuple(x * (1.0 - fraction) + y * fraction for x, y in zip(a, b))


    def graph_value_colors(self, values, base=None):
        # the longer the bar the deeper the color, square root scaled
        # so small bars stay distinguishable next to a dominating one
        style = self.graph_style()
        vmax = float(max(values)) if values and max(values) > 0 else 1.0
        colors = []
        if base is not None:
            # multi series charts keep their identity hue
            pale = self.graph_blend(base, style['bg'], 0.55)
            deep = self.graph_blend(base, style['ink'], 0.25)
            for value in values:
                t = 0.15 + 0.85 * math.sqrt(max(value, 0) / vmax)
                colors.append(self.graph_blend(pale, deep, min(t, 1.0)))
            return colors
        # single series ride the plasma colormap, largest value in
        # deep purple, smallest towards yellow
        cmap = matplotlib.colormaps['plasma']
        lo, hi = style['ramp']
        for value in values:
            t = math.sqrt(max(value, 0) / vmax)
            colors.append(cmap(hi - t * (hi - lo)))
        return colors


    def graph_grid(self, ax, axis):
        style = self.graph_style()
        ax.grid(True, axis=axis, color=style['grid'], linewidth=0.7)
        ax.set_axisbelow(True)
        # the grid axis carries the counters, integers only
        locator = matplotlib.ticker.MaxNLocator(integer=True)
        if axis == 'y':
            ax.yaxis.set_major_locator(locator)
        else:
            ax.xaxis.set_major_locator(locator)


    def graph_bar_labels(self, ax, bars, horizontal=False, fmt='%d', total=None):
        style = self.graph_style()
        for bar in bars:
            if horizontal:
                value, xy = bar.get_width(), \
                        (bar.get_width(), bar.get_y() + bar.get_height() / 2)
                if value < 0:
                    offset, ha, va = (-3, 0), 'right', 'center'
                else:
                    offset, ha, va = (3, 0), 'left', 'center'
            else:
                value, xy = bar.get_height(), \
                        (bar.get_x() + bar.get_width() / 2, bar.get_height())
                offset, ha, va = (0, 2), 'center', 'bottom'
            label = fmt % (value)
            if total:
                # two lines for vertical bars, neighbor labels collide else
                separator = ' ' if horizontal else '\n'
                label += "%s(%.1f%%)" % (separator, (float(value) / total) * 100.0)
            ax.annotate(label, xy, xytext=offset,
                        textcoords='offset points', ha=ha, va=va,
                        fontsize=7, color=style['ink'], zorder=4)


    def graph_proportion_row(self, ax, y, parts, labels, colors, caption):
        # one horizontal 100 percent bar, segments labeled inline
        style = self.graph_style()
        total = sum(parts)
        if total == 0:
            return
        left = 0.0
        for part, label, color in zip(parts, labels, colors):
            fraction = float(part) / total
            ax.barh(y, fraction, left=left, height=0.42, color=color, zorder=2)
            if fraction > 0.08:
                ax.text(left + fraction / 2, y,
                        "%s  %d (%.0f%%)" % (label, part, fraction * 100.0),
                        ha='center', va='center', fontsize=8,
                        color=style['bg'], zorder=3)
            left += fraction
        ax.text(0.0, y + 0.34, caption, ha='left', va='bottom', fontsize=8,
                color=style['ink'])


    def graph_render(self, fig, filename, description=None):
        style = self.graph_style()
        if getattr(self.opts, 'graph_transparent', False):
            fig.savefig(filename, dpi=300, transparent=True)
        else:
            fig.savefig(filename, dpi=300, facecolor=style['bg'])
        plt.close(fig)
        sys.stderr.write("# graph written: %s\n" % (filename))
        if description:
            text, x_axis, y_axis = description
            paragraphs = [textwrap.fill(' '.join(p.split()), width=72)
                          for p in text.strip().split('\n\n')]
            paragraphs.append('\n'.join((
                textwrap.fill("X axis: %s" % (x_axis), width=72,
                              subsequent_indent='        '),
                textwrap.fill("Y axis: %s" % (y_axis), width=72,
                              subsequent_indent='        '))))
            with open('%s.txt' % (filename), 'w', encoding='utf-8') as f:
                f.write('\n\n'.join(paragraphs) + '\n')
            sys.stderr.write("# graph description: %s.txt\n" % (filename))


    def write_json(self, module, data, binary=None):
        if not getattr(self.opts, 'json_out', None):
            return
        path = self.opts.json_out
        directory = os.path.dirname(path)
        if directory:
            os.makedirs(directory, exist_ok=True)
        document = { 'module': module, 'data': data }
        if binary is None:
            binary = getattr(self.opts, 'filename', None)
        if binary is not None:
            document['binary'] = os.path.abspath(binary)
        with open(path, 'w', encoding='utf-8') as f:
            json.dump(document, f, indent=2, sort_keys=True)
            f.write('\n')
        sys.stderr.write("# json written: %s\n" % (path))


    def graph_skip(self, filename):
        sys.stderr.write("# graph skipped, no data: %s\n" % (filename))



class Parser:

    def __init__(self, opts):
        self.args = opts
        self.filename = opts.filename


    def init_disassembler(self, elffile):
        if elffile.elfclass == 64:
            mode = capstone.CS_MODE_64
        else:
            mode = capstone.CS_MODE_32
        md = capstone.Cs(capstone.CS_ARCH_X86, mode)
        # AT&T syntax keeps the mnemonics compatible with the
        # instruction database and the heuristic classifier
        md.syntax = capstone.CS_OPT_SYNTAX_ATT
        md.detail = True
        # embedded data (jump tables etc.) must not stop the engine
        md.skipdata = True
        return md


    def executable_sections(self, elffile):
        sections = []
        for section in elffile.iter_sections():
            if section['sh_flags'] & SH_FLAGS.SHF_EXECINSTR == 0:
                continue
            if section['sh_type'] == 'SHT_NOBITS':
                continue
            sections.append([section['sh_addr'], section['sh_addr'] + section['sh_size'],
                             section.name, section.data()])
        sections.sort(key=lambda s: s[0])
        return sections


    def section_by_addr(self, sections, addr):
        for start, end, name, data in sections:
            if start <= addr < end:
                return start, end, name, data
        return None


    def collect_functions(self, elffile, sections):
        functions = []
        symtab = elffile.get_section_by_name('.symtab')
        if symtab is None:
            # distro binaries are usually stripped down to the dynamic
            # symbol table, better than no function information at all
            symtab = elffile.get_section_by_name('.dynsym')
            if symtab is not None:
                self.caller.err(
                        "Warning: no .symtab, using the dynamic symbol table "
                        "(.dynsym) - static functions are invisible and "
                        "attributed to their preceding exported function\n")
        if symtab is None:
            return functions
        seen_addrs = set()
        for sym in symtab.iter_symbols():
            if sym['st_info']['type'] != 'STT_FUNC':
                continue
            addr = sym['st_value']
            if addr in seen_addrs:
                # alias symbol, the first one wins
                continue
            if self.section_by_addr(sections, addr) is None:
                continue
            seen_addrs.add(addr)
            functions.append([addr, sym['st_size'], sym.name])
        functions.sort(key=lambda f: f[0])

        # symbols without a size (hand written assembly) span
        # until the next function or the section end
        for i, func in enumerate(functions):
            if func[1] != 0:
                continue
            end = self.section_by_addr(sections, func[0])[1]
            if i + 1 < len(functions):
                end = min(end, functions[i + 1][0])
            func[1] = end - func[0]
        return functions


    def pseudo_functions(self, sections):
        # no symbol table available: treat every executable
        # section as one big function
        return [[start, end - start, name] for start, end, name, data in sections]


    def split_operands(self, op_str):
        # split "$0x10, -0x210(%rbp,%rax,1)" at commas outside parentheses
        ops = []
        depth = 0
        current = ''
        for char in op_str:
            if char == '(':
                depth += 1
            elif char == ')':
                depth -= 1
            if char == ',' and depth == 0:
                ops.append(current.strip())
                current = ''
            else:
                current += char
        if current.strip():
            ops.append(current.strip())
        return ops


    def build_atom(self, insn):
        opcode = ' '.join('%02x' % (b) for b in insn.bytes)
        line = '%x:\t%s\t%s\t%s' % (insn.address, opcode, insn.mnemonic, insn.op_str)
        self.caller.debug("%s\n" % (line))

        jmp_addr = None
        is_jump = insn.group(capstone.CS_GRP_JUMP)
        if is_jump or insn.group(capstone.CS_GRP_CALL):
            operands = insn.operands
            if operands and operands[0].type == capstone.x86.X86_OP_IMM:
                jmp_addr = operands[0].imm

        d = dict()
        d['mnemonic'] = insn.mnemonic
        ops = self.split_operands(insn.op_str)
        if len(ops) >= 2:
            # AT&T operand order: source(s) first, destination last
            d['src'] = ops[0]
            d['dst'] = ops[-1]
            atom = BinaryAtom(BinaryAtom.TYPE_2, line, insn.address, opcode, d)
        elif len(ops) == 1:
            d['src'] = ops[0]
            atom = BinaryAtom(BinaryAtom.TYPE_5, line, insn.address, opcode, d)
        else:
            atom = BinaryAtom(BinaryAtom.TYPE_6, line, insn.address, opcode, d)
        atom.jmp_addr = jmp_addr
        atom.is_jump = is_jump
        return atom


    # capstone's python binding materializes the result of a disasm()
    # call as a whole, so large ranges are diced into chunks to keep
    # the memory usage bounded
    DISASM_CHUNK = 1 << 18
    # maximal instruction length is 15 byte, per
    # "Intel 64 and IA-32 Architectures Software Developer's Manual"
    MAX_INSN_LEN = 16

    def disasm_range(self, md, code, addr):
        pos = 0
        total = len(code)
        while pos < total:
            chunk_end = min(pos + Parser.DISASM_CHUNK, total)
            final = chunk_end == total
            # an instruction may straddle the chunk boundary, hold
            # back the last bytes and re-decode them in the next round
            limit = chunk_end if final else chunk_end - Parser.MAX_INSN_LEN
            progress = pos
            for insn in md.disasm(code[pos:chunk_end], addr + pos):
                end = insn.address + insn.size - addr
                if end > limit:
                    break
                yield insn
                progress = end
            if progress == pos:
                break
            pos = progress


    def disassemble_function(self, md, sections, addr, size, name, context):
        section = self.section_by_addr(sections, addr)
        if section is None:
            return
        sec_start, sec_end, sec_name, data = section
        context.function_name = name
        context.function_start_address = addr
        context.function_size = size
        context.section_name = sec_name
        self.caller.debug("function %s at 0x%x, %d byte, section %s\n" %
                (name, addr, size, sec_name))

        offset = addr - sec_start
        code = data[offset:offset + size]
        for insn in self.disasm_range(md, code, addr):
            if insn.id == 0:
                # skipdata placeholder, embedded non-code bytes
                continue
            self.caller.process(context, self.build_atom(insn))


    def process(self, filename):
        start_time = time.monotonic()
        with open(filename, 'rb') as f:
            elffile = ELFFile(f)
            md = self.init_disassembler(elffile)
            sections = self.executable_sections(elffile)
            functions = self.collect_functions(elffile, sections)
            if not functions:
                self.caller.err(
                        "Warning: no function symbols found (stripped binary?), "
                        "falling back to section granularity\n"
                        "Warning: function based analyses are unreliable now, "
                        "especially local jump detection - every jump within "
                        "a section counts as function local\n")
                functions = self.pseudo_functions(sections)
            context = Context()
            for addr, size, name in functions:
                self.disassemble_function(md, sections, addr, size, name, context)
        end_time = time.monotonic()
        self.caller.verbose("pass one took %.2f seconds\n" % (end_time - start_time))

        return


    def run(self, caller):
        self.caller = caller
        self.caller.msg("Instruction and Opcode Analyzer - (C) 2014-2021\n")
        self.caller.verbose("URL: https://github.com/hgn/instruction-layout-analyzer\n")
        self.caller.verbose("Binary to analyze: %s\n" % self.args.filename)
        statinfo = os.stat(self.args.filename)
        if statinfo.st_size > 1000000:
            self.caller.verbose("File larger then 1MByte, analysis may take some time\n")

        self.process(self.args.filename)



class FunctionAnalyzer(Common):

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.func_excluded = 0
        self.parse_local_options()
        self.db = dict()
        self.db_duplicates = dict()
        self.strlen_longest_funcname = 10
        self.strlen_largest_size = 4
        self.biggest_function = 0


    GRAPHS = [
        ('sizes', 'function-sizes.png', 'largest functions'),
        ('histogram', 'function-histogram.png', 'function size distribution'),
        ('cumulative', 'function-cumulative.png', 'cumulative code share'),
        ('alignment', 'function-alignment.png', 'function start alignment'),
    ]

    def parse_local_options(self):
        parser = module_parser("function",
                "Function anatomy: sizes, duplicates, prologues and alignment.")
        add_graph_arguments(parser, FunctionAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, FunctionAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def process_function_pro_epi_logue(self, context, atom, mnemonic_db):
        if mnemonic_db['cnt'] < 4:
            # we capture the first 10 instructions per functions
            mnemonic_db[mnemonic_db['cnt']] = atom.mnemonic
            mnemonic_db['captured'] += 1
        # this will overwriten each time, at the end this entry will hold
        # the last mnemonic for the function
        mnemonic_db['-1'] = atom.mnemonic
        mnemonic_db['cnt'] += 1


    def process_function_duplicate_check(self, context):
        if not context.function_name in self.db_duplicates:
            self.db_duplicates[context.function_name] = dict()
            self.db_duplicates[context.function_name][context.function_start_address] = True
            return
        self.db_duplicates[context.function_name][context.function_start_address] = True


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            self.func_excluded += 1
            return
        self.process_function_duplicate_check(context)
        self.strlen_longest_funcname = max(len(context.function_name), self.strlen_longest_funcname)
        func_id = "%s:%s" % (context.function_name, context.function_start_address)
        if not func_id in self.db:
            self.db[func_id] = dict()
            self.db[func_id]['start'] = \
                    context.function_start_address
            self.db[func_id]['end'] = \
                    context.function_start_address + atom.opcode_len
            self.db[func_id]['size'] = atom.opcode_len
            self.db[func_id]['mnemonic'] = dict()
            self.db[func_id]['mnemonic']['cnt'] = 0
            self.db[func_id]['mnemonic']['captured'] = 0
            self.process_function_pro_epi_logue(context, atom, self.db[func_id]['mnemonic'])
            self.biggest_function = max(self.db[func_id]['size'], self.biggest_function)
            return

        self.db[func_id]['end'] += atom.opcode_len
        self.db[func_id]['size'] += atom.opcode_len
        self.strlen_largest_size = max(len(str(self.db[func_id]['size'])), self.strlen_largest_size)
        self.biggest_function = max(self.db[func_id]['size'], self.biggest_function)
        # last mnemonic in function
        self.process_function_pro_epi_logue(context, atom, self.db[func_id]['mnemonic'])


    def show(self, json=False):
        self.show_human()
        self.write_json('function', self.json_data())


    def json_data(self):
        functions = []
        for func_id, value in sorted(self.db.items(),
                key=lambda item: item[1]['size'], reverse=True):
            functions.append({
                'name': func_id.split(':')[0],
                'start': value['start'],
                'end': value['end'],
                'size': value['size'],
            })
        histogram = dict()
        alignment = dict()
        if self.db:
            i = 2
            while i <= self.next_power_of_two(self.biggest_function):
                histogram[str(i)] = 0
                i *= 2
            for value in self.db.values():
                histogram[str(self.next_power_of_two(value['size']))] += 1
            addr_list = [128, 64, 32, 16, 8, 4, 2, 0]
            alignment = dict((str(a), 0) for a in addr_list)
            for value in self.db.values():
                alignment[str(self.determine_addr_alignment(
                        addr_list, value['start']))] += 1
        duplicates = dict((name, len(addrs)) for name, addrs
                          in self.db_duplicates.items() if len(addrs) > 1)
        # aggregate the function prologues (first three mnemonics) so the
        # mass analysis can find the standard prologue across a system
        prologues = dict()
        for value in self.db.values():
            mnem = value['mnemonic']
            if mnem['captured'] < 3:
                continue
            sig = '%s,%s,%s' % (mnem[0], mnem[1], mnem[2])
            prologues[sig] = prologues.get(sig, 0) + 1
        return {
            'functions-analyzed': len(self.db),
            'functions-excluded': self.func_excluded,
            'biggest-function': self.biggest_function,
            'functions': functions,
            'size-histogram': histogram,
            'alignment': alignment,
            'duplicates': duplicates,
            'prologues': prologues,
        }


    def show_function_duplicates(self):
        printed_header = False
        fmt = "%%%d.%ds: %%3d duplicates\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname)
        for key in sorted(self.db_duplicates.items(), key=lambda item: len(item[1]), reverse=True):
            if len(key[1]) <= 1:
                break
            if not printed_header:
                self.msg_underline("Function Duplicates", pre_news=2, post_news=2)
                printed_header = True
            self.msg(fmt % (key[0], len(key[1])))



    def graph_size_histogram(self, histogram):
        style = self.graph_style()
        buckets = sorted(histogram.keys())
        counts = [histogram[b] for b in buckets]
        fig, ax = self.graph_axes(xlabel='Function Size [Byte]', ylabel='Functions')
        self.graph_grid(ax, 'y')
        x = range(len(buckets))
        bars = ax.bar(x, counts, width=0.72, color=self.graph_value_colors(counts))
        ax.set_xticks(list(x))
        ax.set_xticklabels(["<= %d" % (b) for b in buckets], rotation=45, ha='right')
        ax.margins(y=0.10)
        self.graph_bar_labels(ax, bars, total=sum(counts))
        self.graph_render(fig, self.opts.graph_histogram_filename,
                GRAPH_DESCRIPTIONS['function-histogram'])


    def graph_top_sizes(self):
        if not self.db:
            self.graph_skip(self.opts.graph_sizes_filename)
            return
        style = self.graph_style()
        entries = sorted(self.db.items(), key=lambda item: item[1]['size'],
                reverse=True)[:20]
        names = [key.split(':')[0] for key, value in entries]
        sizes = [value['size'] for key, value in entries]
        code_size = sum(value['size'] for key, value in self.db.items())
        fig, ax = self.graph_axes(xlabel='Function Size [Byte]')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, sizes, height=0.72, color=self.graph_value_colors(sizes))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.08)
        self.graph_bar_labels(ax, bars, horizontal=True, total=code_size)
        self.graph_render(fig, self.opts.graph_sizes_filename,
                GRAPH_DESCRIPTIONS['function-sizes'])


    def graph_cumulative_share(self):
        if not self.db:
            self.graph_skip(self.opts.graph_cumulative_filename)
            return
        style = self.graph_style()
        sizes = sorted((value['size'] for value in self.db.values()), reverse=True)
        total = sum(sizes)
        if total == 0:
            self.graph_skip(self.opts.graph_cumulative_filename)
            return
        n = len(sizes)
        x, y = [], []
        cum = 0
        for i, size in enumerate(sizes):
            cum += size
            x.append((i + 1) * 100.0 / n)
            y.append(cum * 100.0 / total)

        fig, ax = self.graph_axes(xlabel='Functions, Largest First [%]',
                ylabel='Cumulative Code Share [%]')
        self.graph_grid(ax, 'y')
        ax.plot(x, y, color=style['primary'], linewidth=1.8)
        ax.fill_between(x, y, color=style['primary'], alpha=0.12, linewidth=0)
        # where does half and most of the code live
        for mark in (50, 90):
            idx = next(i for i, v in enumerate(y) if v >= mark)
            ax.plot([x[idx]], [y[idx]], 'o', color=style['secondary'],
                    markersize=5, zorder=4)
            ax.annotate("%d%% of the code in %.1f%% of the functions" %
                        (mark, x[idx]), (x[idx], y[idx]), xytext=(10, -4),
                        textcoords='offset points', fontsize=8,
                        color=style['ink'])
        ax.set_xlim(0, 100)
        ax.set_ylim(0, 104)
        self.graph_render(fig, self.opts.graph_cumulative_filename,
                GRAPH_DESCRIPTIONS['function-cumulative'])


    def graph_start_alignment(self):
        if not self.db:
            self.graph_skip(self.opts.graph_alignment_filename)
            return
        style = self.graph_style()
        addr_list = [128, 64, 32, 16, 8, 4, 2, 0]
        counts = dict((a, 0) for a in addr_list)
        for key, value in self.db.items():
            counts[self.determine_addr_alignment(addr_list, value['start'])] += 1
        labels = ["%d Byte" % (a) if a else "Unaligned" for a in addr_list]
        fig, ax = self.graph_axes(xlabel='Functions', figsize=(8.0, 3.4))
        self.graph_grid(ax, 'x')
        y = range(len(addr_list))
        bars = ax.barh(y, [counts[a] for a in addr_list], height=0.72,
                color=self.graph_value_colors([counts[a] for a in addr_list]))
        ax.set_yticks(list(y))
        ax.set_yticklabels(labels)
        ax.margins(x=0.08)
        self.graph_bar_labels(ax, bars, horizontal=True, total=len(self.db))
        self.graph_render(fig, self.opts.graph_alignment_filename,
                GRAPH_DESCRIPTIONS['function-alignment'])


    def show_function_size_histogram(self):
        histogram = dict()
        histogram[1] = 0 # just for the case
        i = 2
        while i <= self.next_power_of_two(self.biggest_function):
            histogram[i] = 0
            i *= 2

        for k,v in self.db.items():
            power_size = self.next_power_of_two(v['size'])
            histogram[power_size] += 1

        overall = len(self.db)
        i = 2
        self.msg_underline("Functions Size Histogram", pre_news=2, post_news=2)
        while i <= self.next_power_of_two(self.biggest_function):
            percent = (float(histogram[i]) / (overall)) * 100.0
            self.msg("<= %6d byte:   %5d   [ %5.2f%% ]\n" % (i, histogram[i], percent))
            i *= 2

        if self.opts.graph_histogram:
            self.graph_size_histogram(histogram)


    def show_common_information(self):
        self.msg_underline("Common Information", pre_news=2, post_news=2)

        smallest_function = sys.maxsize
        for key, value in self.db.items():
            smallest_function = min(value['size'], smallest_function)

        functions_no = len(self.db)
        self.msg("Number of analyzed functions: %d\n" % (functions_no))
        if self.func_excluded > 0:
            self.msg("Number of excluded functions: %d\n" % (self.func_excluded))
        self.msg("Biggest function size: %d byte\n" % (self.biggest_function))
        if smallest_function != sys.maxsize:
            self.msg("Smallest function size: %d byte\n" % (smallest_function))


    def determine_addr_alignment(self, addr_list, address):
        for addr_entry in addr_list:
            if addr_entry == 0:
                return 0
            if address % addr_entry == 0:
                return addr_entry


    def show_function_alignment_info(self):
        addr_list = [ 128, 64, 32, 16, 8, 4, 2, 0]
        no_functions = 0
        self.msg_underline("Function Alignment Info", pre_news=2, post_news=2)
        msg = "{:<11} {:>}\n".format("Alignment", 'No Functions [Percent]')
        self.msg(msg)
        db = dict()
        for addr_entry in addr_list:
            db[addr_entry] = dict()
            db[addr_entry]['functions'] = list()

        for key, value in self.db.items():
            db[self.determine_addr_alignment(addr_list, value['start'])]['functions'].append(key.split(':')[0])
            no_functions += 1

        for addr_entry in addr_list:
            percent = (float(len(db[addr_entry]['functions'])) / (no_functions))
            msg = "{:>8}:   {:<}  [ {:>6.2%} ]\n".format(addr_entry, len(db[addr_entry]['functions']), percent)
            self.msg(msg)


    def show_human(self):
        # Some overall information about functions
        # Number of Functions, average len, min length, max length, etc
        self.show_common_information()
        self.msg_underline("Functions Size", pre_news=1, post_news=2)
        fmt = "%%%d.%ds: %%%dd byte  [start: 0x%%x, end: 0x%%x]\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname, self.strlen_largest_size)
        for key in sorted(self.db.items(), key=lambda item: item[1]['size'], reverse=True):
            self.msg(fmt % (key[0].split(':')[0], key[1]['size'], key[1]['start'], key[1]['end']))

        self.show_function_size_histogram()

        # Function Mnemonic Signature Overview
        similar_data = dict()
        for key, value in self.db.items():
            if self.opts.verbose:
                self.msg("%s:\n" % (key.split(':')[0]))
            signature = ""
            seq = list()
            for i in range(self.db[key]['mnemonic']['captured']):
                if self.opts.verbose:
                    self.msg("\t%d %s\n" % (i, self.db[key]['mnemonic'][i]))
                signature += self.db[key]['mnemonic'][i]
                seq.append(self.db[key]['mnemonic'][i])
            if signature in similar_data:
                similar_data[signature]['cnt'] += 1
            else:
                similar_data[signature] = dict()
                similar_data[signature]['cnt'] = 1
                similar_data[signature]['seq'] = seq
                similar_data[signature]['signature'] = signature

        self.show_function_duplicates()

        self.msg_underline("Functions Prologue Similarity", pre_news=2, post_news=2)
        self.msg("No Functions    Function Prologue\n")
        for key in sorted(similar_data.items(), key=lambda item: item[1]['cnt'], reverse=True):
            self.msg("%-6d          %s\n" % (key[1]['cnt'], key[1]['seq']))

        self.show_function_alignment_info()

        if self.opts.graph_sizes:
            self.graph_top_sizes()
        if self.opts.graph_cumulative:
            self.graph_cumulative_share()
        if self.opts.graph_alignment:
            self.graph_start_alignment()


    def show_json(self):
        pass



class InstructionAnalyzer(Common):

    def __init__(self):
        self.parse_local_options()
        self.instructions = dict()
        self.sum_opcode_length = 0
        self.max_opcode_length = 0
        self.db_category = dict()


    GRAPHS = [
        ('categories', 'instruction-categories.png', 'instruction category distribution'),
        ('mnemonics', 'instruction-mnemonics.png', 'most frequent mnemonics'),
        ('lengths', 'instruction-lengths.png', 'instruction length distribution'),
        ('ranges', 'instruction-ranges.png', 'encoding length ranges per mnemonic'),
    ]

    def parse_local_options(self):
        parser = module_parser("instruction",
                "Instruction mix: mnemonics, categories and encoding lengths.",
                no_exclude=False)
        add_graph_arguments(parser, InstructionAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, InstructionAnalyzer.GRAPHS)

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def add_existing(self, atom):
        self.instructions[atom.mnemonic]['count'] += 1
        # now account instruction length variability
        if atom.opcode_len in self.instructions[atom.mnemonic]['instruction-lengths']:
            self.instructions[atom.mnemonic]['instruction-lengths'][atom.opcode_len] += 1
        else:
            self.instructions[atom.mnemonic]['instruction-lengths'][atom.opcode_len] = 1


    def add_new(self, atom):
        self.instructions[atom.mnemonic] = dict()
        self.instructions[atom.mnemonic]['count'] = 1
        self.instructions[atom.mnemonic]['category'] = InstructionCategory.guess(atom.mnemonic)
        # ok, this is more complicated but it is suitable for large
        # projects with millions of instructions
        self.instructions[atom.mnemonic]['instruction-lengths'] = dict()
        self.instructions[atom.mnemonic]['instruction-lengths'][atom.opcode_len] = 1


    def process_category(self, atom):
        cat = InstructionCategory.guess(atom.mnemonic)
        if cat in self.db_category:
            self.db_category[cat] += 1
        else:
            self.db_category[cat] = 1


    def process(self, context, atom):
        self.max_opcode_length = max(self.max_opcode_length, atom.opcode_len)
        self.sum_opcode_length += atom.opcode_len
        if atom.mnemonic in self.instructions:
            self.add_existing(atom)
        else:
            self.add_new(atom)
        self.process_category(atom)


    def show_general(self, no_instructions):
        self.msg("General Information:\n")
        self.msg("    Number Instructions: %d\n" % (no_instructions))
        self.msg("    Number different Instructions: %d\n" % (len(self.instructions.keys())))
        self.msg("    Overall Opcode length: %d byte\n" % (self.sum_opcode_length))
        self.msg("    Maximal Opcode length: %d byte\n" % (self.max_opcode_length))
        self.msg("\n")

        self.msg_underline("Detailed Analysis", pre_news=2, post_news=3)

        self.msg("  Instruction  |  Count    [    %]  |    Category  | Length (avg, min, max)\n")
        self.msg("--------------------------------------------------------------------\n")
        for k in sorted(self.instructions.items(), key=lambda item: item[1]['count'], reverse=True):
            minval = min(k[1]['instruction-lengths'].keys())
            maxval = max(k[1]['instruction-lengths'].keys())
            sumval = 0.0
            for key, value in k[1]['instruction-lengths'].items():
                sumval += float(key) * float(value)
            sumval /= float(k[1]['count'])
            percent = (float(k[1]['count']) / (no_instructions)) * 100.0
            self.msg("%15.15s %10d [%5.2f]  %13.13s      %5.1f,%3.d,%3.d\n" %
                (k[0], k[1]['count'], percent, InstructionCategory.str(k[1]['category']), sumval, minval, maxval))


    def json_data(self, overall):
        mnemonics = []
        for name, value in sorted(self.instructions.items(),
                key=lambda item: item[1]['count'], reverse=True):
            lengths = value['instruction-lengths']
            avg = sum(l * c for l, c in lengths.items()) / float(value['count'])
            mnemonics.append({
                'mnemonic': name,
                'count': value['count'],
                'category': InstructionCategory.str(value['category']),
                'length-avg': round(avg, 2),
                'length-min': min(lengths.keys()),
                'length-max': max(lengths.keys()),
            })
        categories = dict((InstructionCategory.str(cat), cnt)
                          for cat, cnt in self.db_category.items())
        length_histogram = dict()
        for value in self.instructions.values():
            for length, cnt in value['instruction-lengths'].items():
                key = str(length)
                length_histogram[key] = length_histogram.get(key, 0) + cnt
        return {
            'instructions': overall,
            'distinct-mnemonics': len(self.instructions),
            'opcode-bytes': self.sum_opcode_length,
            'max-opcode-length': self.max_opcode_length,
            'mnemonics': mnemonics,
            'categories': categories,
            'length-histogram': length_histogram,
        }


    def graph_category_histogram(self, entries):
        style = self.graph_style()
        names = [InstructionCategory.str(key) for key, cnt in entries]
        counts = [cnt for key, cnt in entries]
        fig, ax = self.graph_axes(xlabel='Instructions')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.08)
        self.graph_bar_labels(ax, bars, horizontal=True, total=self.no_instructions)
        self.graph_render(fig, self.opts.graph_categories_filename,
                GRAPH_DESCRIPTIONS['instruction-categories'])


    def graph_top_mnemonics(self):
        if not self.instructions:
            self.graph_skip(self.opts.graph_mnemonics_filename)
            return
        style = self.graph_style()
        entries = sorted(self.instructions.items(),
                key=lambda item: item[1]['count'], reverse=True)[:20]
        names = [key for key, value in entries]
        counts = [value['count'] for key, value in entries]
        fig, ax = self.graph_axes(xlabel='Instructions')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names, family='monospace')
        ax.invert_yaxis()
        ax.margins(x=0.08)
        self.graph_bar_labels(ax, bars, horizontal=True, total=self.no_instructions)
        self.graph_render(fig, self.opts.graph_mnemonics_filename,
                GRAPH_DESCRIPTIONS['instruction-mnemonics'])


    def graph_length_histogram(self):
        if not self.instructions:
            self.graph_skip(self.opts.graph_lengths_filename)
            return
        style = self.graph_style()
        histogram = dict()
        for value in self.instructions.values():
            for length, cnt in value['instruction-lengths'].items():
                histogram[length] = histogram.get(length, 0) + cnt
        lengths = list(range(1, max(histogram.keys()) + 1))
        counts = [histogram.get(l, 0) for l in lengths]
        fig, ax = self.graph_axes(xlabel='Instruction Length [Byte]',
                ylabel='Instructions')
        self.graph_grid(ax, 'y')
        bars = ax.bar(lengths, counts, width=0.72, color=self.graph_value_colors(counts))
        ax.set_xticks(lengths)
        ax.margins(y=0.10)
        self.graph_bar_labels(ax, bars, total=self.no_instructions)
        self.graph_render(fig, self.opts.graph_lengths_filename,
                GRAPH_DESCRIPTIONS['instruction-lengths'])


    def graph_length_ranges(self):
        if not self.instructions:
            self.graph_skip(self.opts.graph_ranges_filename)
            return
        style = self.graph_style()
        entries = sorted(self.instructions.items(),
                key=lambda item: item[1]['count'], reverse=True)[:20]
        names, avgs, mins, maxs = [], [], [], []
        for name, value in entries:
            lengths = value['instruction-lengths']
            avg = sum(l * c for l, c in lengths.items()) / float(value['count'])
            names.append(name)
            avgs.append(avg)
            mins.append(min(lengths.keys()))
            maxs.append(max(lengths.keys()))

        fig, ax = self.graph_axes(xlabel='Encoding Length [Byte]')
        self.graph_grid(ax, 'x')
        y = list(range(len(names)))
        ax.hlines(y, mins, maxs, color=style['frame'], linewidth=1.4,
                zorder=2, label='Min-Max Span')
        ax.plot(mins, y, '|', color=style['frame'], markersize=7, zorder=3)
        ax.plot(maxs, y, '|', color=style['frame'], markersize=7, zorder=3)
        ax.plot(avgs, y, 'o', color=style['primary'], markersize=6,
                zorder=4, linestyle='none', label='Average')
        ax.set_yticks(y)
        ax.set_yticklabels(names, family='monospace')
        ax.invert_yaxis()
        ax.set_xticks(range(0, max(maxs) + 2))
        ax.set_xlim(0, max(maxs) + 1)
        ax.legend(frameon=False, fontsize=8, labelcolor=style['ink'])
        self.graph_render(fig, self.opts.graph_ranges_filename,
                GRAPH_DESCRIPTIONS['instruction-ranges'])


    def show_categories(self, no_instructions):
        self.msg_underline("Instruction Category", pre_news=2, post_news=3)
        ret = self.msg("{:<20}| {:<10}\n".format("Category", "Number of Instructions"))
        self.line(ret)
        entries = sorted(self.db_category.items(), key=lambda item: item[1], reverse=True)
        for key, cnt in entries:
            cat_name = InstructionCategory.str(key)
            percent = (float(cnt) / (no_instructions)) * 100.0
            self.msg("{:<20}  {:>8} [{:>6.2f} %]\n".format(cat_name, cnt, percent))

        if self.opts.graph_categories:
            self.graph_category_histogram(entries)


    def show(self, json=False):
        overall = 0
        for key, value in self.instructions.items():
            overall += value['count']
        self.no_instructions = overall

        self.msg("Program Instructions Analyses:\n\n")

        self.show_general(overall)
        self.show_categories(overall)
        self.write_json('instruction', self.json_data(overall))

        if self.opts.graph_mnemonics:
            self.graph_top_mnemonics()
        if self.opts.graph_lengths:
            self.graph_length_histogram()
        if self.opts.graph_ranges:
            self.graph_length_ranges()




class BranchAnalyzer(Common):

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.db = dict()
        self.all = self.new_direction_db()
        self.forward = self.new_direction_db()
        self.backward = self.new_direction_db()
        self.conditional = 0
        self.unconditional = 0
        self.strlen_longest_funcname = 10


    GRAPHS = [
        ('histogram', 'branch-histogram.png', 'jump distance distribution'),
        ('direction', 'branch-direction.png', 'jump direction and condition shares'),
        ('percentiles', 'branch-percentiles.png', 'jump distance percentile curves'),
    ]

    def parse_local_options(self):
        parser = module_parser("branch",
                "Local jumps: direction, condition and distance distribution.")
        add_graph_arguments(parser, BranchAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, BranchAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def new_direction_db(self):
        return {
            'cnt': 0,
            'sum': 0,
            'min': sys.maxsize,
            'max': 0,
            'histogram': dict(),
            'values': array.array('q')
        }


    def account_direction(self, direction_db, distance):
        direction_db['cnt'] += 1
        direction_db['sum'] += distance
        direction_db['min'] = min(direction_db['min'], distance)
        direction_db['max'] = max(direction_db['max'], distance)
        bucket = self.next_power_of_two(max(distance, 1))
        if bucket in direction_db['histogram']:
            direction_db['histogram'][bucket] += 1
        else:
            direction_db['histogram'][bucket] = 1


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        if not atom.is_jump or atom.jmp_addr is None:
            return

        start = context.function_start_address
        end = start + context.function_size
        if not start <= atom.jmp_addr < end:
            # tail call or long jump, target outside the function
            return

        # capstone may prepend a prefix to the mnemonic (notrack jmpq)
        if atom.mnemonic.split()[-1].startswith('jmp'):
            self.unconditional += 1
        else:
            self.conditional += 1

        func_id = "%s:%s" % (context.function_name, start)
        if func_id not in self.db:
            self.db[func_id] = { 'forward': 0, 'backward': 0 }
            self.strlen_longest_funcname = max(len(context.function_name),
                                               self.strlen_longest_funcname)

        distance = atom.jmp_addr - atom.addr
        self.account_direction(self.all, abs(distance))
        if distance > 0:
            self.account_direction(self.forward, distance)
            self.forward['values'].append(distance)
            self.db[func_id]['forward'] += 1
        else:
            self.account_direction(self.backward, -distance)
            self.backward['values'].append(-distance)
            self.db[func_id]['backward'] += 1


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def show_direction(self, name, direction_db, overall):
        cnt = direction_db['cnt']
        self.msg("%-16s %6d  [ %5.2f%% ]\n" % (name + ':', cnt,
                 self.percent(overall, cnt)))
        if cnt == 0:
            return
        self.msg("    distance min/avg/max: %d / %.1f / %d byte\n" %
                (direction_db['min'], float(direction_db['sum']) / cnt,
                 direction_db['max']))


    def show_histogram(self):
        histogram = self.all['histogram']
        if not histogram:
            return
        self.msg_underline("Jump Distance Histogram", pre_news=2, post_news=2)
        overall = self.all['cnt']
        i = 1
        while i <= max(histogram.keys()):
            cnt = histogram.get(i, 0)
            self.msg("<= %6d byte:   %5d   [ %5.2f%% ]\n" %
                    (i, cnt, self.percent(overall, cnt)))
            i *= 2


    def show_functions(self):
        self.msg_underline("Functions", pre_news=2, post_news=2)
        fmt = "%%%d.%ds: %%8d jumps  [forward: %%d, backward: %%d]\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname)
        entries = sorted(self.db.items(),
                key=lambda item: item[1]['forward'] + item[1]['backward'],
                reverse=True)
        for func_id, value in entries:
            self.msg(fmt % (func_id.split(':')[0],
                     value['forward'] + value['backward'],
                     value['forward'], value['backward']))


    def json_direction(self, db):
        data = {
            'count': db['cnt'],
            'histogram': dict((str(k), v) for k, v in db['histogram'].items()),
        }
        if db['cnt']:
            values = sorted(db['values'])
            n = len(values)
            data['distance-min'] = db['min']
            data['distance-max'] = db['max']
            data['distance-avg'] = round(float(db['sum']) / db['cnt'], 2)
            for p in (50, 90, 99):
                data['distance-p%d' % (p)] = values[min(n - 1, (n * p) // 100)]
        return data


    def json_data(self):
        functions = dict()
        for func_id, value in self.db.items():
            functions[func_id.split(':')[0]] = {
                'forward': value['forward'],
                'backward': value['backward'],
            }
        return {
            'jumps': self.all['cnt'],
            'conditional': self.conditional,
            'unconditional': self.unconditional,
            'forward': self.json_direction(self.forward),
            'backward': self.json_direction(self.backward),
            'functions': functions,
        }


    def graph_distance_histogram(self):
        style = self.graph_style()
        buckets = []
        i = 1
        while i <= max(self.all['histogram'].keys()):
            buckets.append(i)
            i *= 2
        forward = [self.forward['histogram'].get(b, 0) for b in buckets]
        backward = [self.backward['histogram'].get(b, 0) for b in buckets]

        fig, ax = self.graph_axes(xlabel='Jump Distance [Byte]', ylabel='Jumps')
        self.graph_grid(ax, 'y')
        x = range(len(buckets))
        width = 0.36
        bars_fw = ax.bar([p - width / 2 for p in x], forward, width=width,
               color=self.graph_value_colors(forward, base=style['primary']))
        bars_bw = ax.bar([p + width / 2 for p in x], backward, width=width,
               color=self.graph_value_colors(backward, base=style['secondary']))
        ax.set_xticks(list(x))
        ax.set_xticklabels(["<= %d" % (b) for b in buckets], rotation=45, ha='right')
        ax.margins(y=0.10)
        handles = [
            matplotlib.patches.Patch(color=style['primary'], label='Forward'),
            matplotlib.patches.Patch(color=style['secondary'], label='Backward'),
        ]
        ax.legend(handles=handles, frameon=False, fontsize=8,
                labelcolor=style['ink'])
        self.graph_render(fig, self.opts.graph_histogram_filename,
                GRAPH_DESCRIPTIONS['branch-histogram'])


    def graph_direction_shares(self):
        style = self.graph_style()
        fig, ax = self.graph_axes(figsize=(8.0, 2.4))
        ax.set_axis_off()
        self.graph_proportion_row(ax, 1.0,
                (self.forward['cnt'], self.backward['cnt']),
                ('Forward', 'Backward'),
                (style['primary'], style['secondary']),
                'Jump Direction')
        self.graph_proportion_row(ax, 0.0,
                (self.conditional, self.unconditional),
                ('Conditional', 'Unconditional'),
                (style['good'], style['bad']),
                'Jump Condition')
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(-0.4, 1.6)
        self.graph_render(fig, self.opts.graph_direction_filename,
                GRAPH_DESCRIPTIONS['branch-direction'])


    def graph_percentile_curves(self):
        style = self.graph_style()
        fig, ax = self.graph_axes(xlabel='Jump Distance [Byte]',
                ylabel='Share of Jumps [%]')
        self.graph_grid(ax, 'y')
        series = (
            (self.forward, 'Forward', style['primary'], True),
            (self.backward, 'Backward', style['secondary'], False),
        )
        for db, name, color, annotate in series:
            values = sorted(db['values'])
            if not values:
                continue
            n = len(values)
            # a few thousand points draw the same curve as millions
            stride = max(1, n // 2000)
            xs = [values[i] for i in range(0, n, stride)] + [values[-1]]
            ys = [(i + 1) * 100.0 / n for i in range(0, n, stride)] + [100.0]
            ax.plot(xs, ys, color=color, linewidth=1.8, label=name)
            for p in (50, 90, 99):
                v = values[min(n - 1, (n * p) // 100)]
                ax.plot([v], [p], 'o', color=color, markersize=5, zorder=4)
                if annotate:
                    ax.annotate("p%d" % (p), (v, p), xytext=(6, -10),
                            textcoords='offset points', fontsize=8,
                            color=style['ink'])
        ax.set_xscale('log')
        ax.set_ylim(0, 104)
        ax.legend(frameon=False, fontsize=8, labelcolor=style['ink'],
                loc='lower right')
        self.graph_render(fig, self.opts.graph_percentiles_filename,
                GRAPH_DESCRIPTIONS['branch-percentiles'])


    def show(self):
        overall = self.all['cnt']
        self.msg_underline("Local Branch Analysis", pre_news=2, post_news=2)
        self.msg("Number of functions with local jumps: %d\n" % (len(self.db)))
        self.msg("Number of local jumps: %d\n\n" % (overall))
        self.show_direction("Forward jumps", self.forward, overall)
        self.show_direction("Backward jumps", self.backward, overall)
        self.msg("\n")
        self.msg("%-16s %6d  [ %5.2f%% ]\n" % ("Conditional:", self.conditional,
                 self.percent(overall, self.conditional)))
        self.msg("%-16s %6d  [ %5.2f%% ]\n" % ("Unconditional:", self.unconditional,
                 self.percent(overall, self.unconditional)))
        self.show_histogram()
        self.show_functions()
        self.write_json('branch', self.json_data())

        if self.opts.graph_histogram:
            if overall > 0:
                self.graph_distance_histogram()
            else:
                self.graph_skip(self.opts.graph_histogram_filename)
        if self.opts.graph_direction:
            if overall > 0:
                self.graph_direction_shares()
            else:
                self.graph_skip(self.opts.graph_direction_filename)
        if self.opts.graph_percentiles:
            if overall > 0:
                self.graph_percentile_curves()
            else:
                self.graph_skip(self.opts.graph_percentiles_filename)




class LayoutAnalyzer(Common):

    GRAPHS = [
        ('map', 'layout-map.png', 'hot/cold layout map of the largest functions'),
        ('split', 'layout-split.png', 'hot versus cold byte share'),
        ('histogram', 'layout-histogram.png', 'cold tail share distribution'),
        ('scatter', 'layout-scatter.png', 'function size versus cold tail share'),
    ]

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.db = dict()
        self.strlen_longest_funcname = 10


    def parse_local_options(self):
        parser = module_parser("layout",
                "Code layout: hot paths, cold tails and frame pointers.")
        add_graph_arguments(parser, LayoutAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, LayoutAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def function_db(self, context):
        func_id = "%s:%s" % (context.function_name, context.function_start_address)
        if func_id not in self.db:
            self.db[func_id] = {
                'name': context.function_name,
                'start': context.function_start_address,
                'size': context.function_size,
                'ret_end': None,
                'targets': [],
                'head': [],
            }
            self.strlen_longest_funcname = max(len(context.function_name),
                                               self.strlen_longest_funcname)
        return self.db[func_id]


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        fdb = self.function_db(context)

        base = re.sub(r'[bwlq]$', '', atom.mnemonic.split()[-1])
        if len(fdb['head']) < 3:
            fdb['head'].append((base, atom.src, atom.dst))

        # the first ret splits the function: everything behind it is
        # code the compiler moved out of the hot path
        if base == 'ret' and fdb['ret_end'] is None:
            fdb['ret_end'] = atom.addr + atom.opcode_len - fdb['start']
            return

        if not atom.is_jump or atom.jmp_addr is None:
            return
        offset = atom.jmp_addr - fdb['start']
        if not 0 <= offset < fdb['size']:
            return
        if atom.mnemonic.split()[-1].startswith('jmp'):
            return
        # local conditional jump, the tail membership of the target
        # is decided later when the first ret is known
        fdb['targets'].append(offset)


    def evaluate(self):
        entries = []
        for func_id, f in self.db.items():
            if f['size'] == 0:
                continue
            entry = dict(f)
            if f['ret_end'] is None:
                entry['cold'] = 0
                entry['tail_jumps'] = 0
            else:
                entry['cold'] = f['size'] - f['ret_end']
                entry['tail_jumps'] = sum(1 for t in f['targets']
                                          if t >= f['ret_end'])
            # the classic frame pointer prologue: push %rbp; mov %rsp,%rbp
            pushes = any(b == 'push' and s == '%rbp' for b, s, d in f['head'])
            moves = any(b == 'mov' and s == '%rsp' and d == '%rbp'
                        for b, s, d in f['head'])
            entry['frame_pointer'] = pushes and moves
            entries.append(entry)
        return entries


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def json_data(self, entries):
        functions = []
        for e in sorted(entries, key=lambda e: e['cold'], reverse=True):
            functions.append({
                'name': e['name'],
                'size': e['size'],
                'cold': e['cold'],
                'tail-jumps': e['tail_jumps'],
                'frame-pointer': e['frame_pointer'],
                'has-ret': e['ret_end'] is not None,
            })
        total = sum(e['size'] for e in entries)
        return {
            'functions-analyzed': len(entries),
            'code-bytes': total,
            'cold-bytes': sum(e['cold'] for e in entries),
            'functions-with-cold-tail': sum(1 for e in entries if e['cold'] > 0),
            'functions-without-ret': sum(1 for e in entries
                                         if e['ret_end'] is None),
            'tail-jumps': sum(e['tail_jumps'] for e in entries),
            'frame-pointer-kept': sum(1 for e in entries if e['frame_pointer']),
            'functions': functions,
        }


    def graph_layout_map(self, entries):
        candidates = sorted((e for e in entries if e['ret_end'] is not None),
                key=lambda e: e['size'], reverse=True)[:25]
        if not candidates:
            self.graph_skip(self.opts.graph_map_filename)
            return
        style = self.graph_style()
        height = max(2.4, 0.8 + 0.26 * len(candidates))
        fig, ax = self.graph_axes(xlabel='Position Within the Function',
                figsize=(8.0, height))
        for i, entry in enumerate(candidates):
            hot = float(entry['ret_end']) / entry['size']
            ax.barh(i, hot, height=0.72, color=style['secondary'])
            ax.barh(i, 1.0 - hot, left=hot, height=0.72, color=style['primary'])
            tails = [float(t) / entry['size'] for t in entry['targets']
                     if t >= entry['ret_end']]
            if tails:
                ax.plot(tails, [i] * len(tails), '|', color=style['ink'],
                        markersize=7, alpha=0.7, zorder=4)
        ax.set_yticks(range(len(candidates)))
        ax.set_yticklabels([e['name'] for e in candidates])
        ax.invert_yaxis()
        ax.set_xlim(0.0, 1.0)
        ax.set_xticks([0.0, 0.25, 0.5, 0.75, 1.0])
        ax.set_xticklabels(['0%', '25%', '50%', '75%', '100%'])
        handles = [
            matplotlib.patches.Patch(color=style['secondary'], label='Hot Head'),
            matplotlib.patches.Patch(color=style['primary'], label='Cold Tail'),
            matplotlib.lines.Line2D([], [], color=style['ink'], marker='|',
                    linestyle='none', label='Jump Into the Tail'),
        ]
        ax.legend(handles=handles, frameon=False, fontsize=8,
                labelcolor=style['ink'], loc='upper center', ncols=3,
                bbox_to_anchor=(0.5, -0.10))
        self.graph_render(fig, self.opts.graph_map_filename,
                GRAPH_DESCRIPTIONS['layout-map'])


    def graph_hot_cold_split(self, entries):
        style = self.graph_style()
        hot = sum(e['size'] - e['cold'] for e in entries)
        cold = sum(e['cold'] for e in entries)
        with_tail = sum(1 for e in entries if e['cold'] > 0)
        frame = sum(1 for e in entries if e['frame_pointer'])
        fig, ax = self.graph_axes(figsize=(8.0, 3.0))
        ax.set_axis_off()
        self.graph_proportion_row(ax, 2.0, (hot, cold),
                ('Hot', 'Cold'),
                (style['secondary'], style['primary']),
                'Code Bytes')
        self.graph_proportion_row(ax, 1.0,
                (with_tail, len(entries) - with_tail),
                ('With Cold Tail', 'Without'),
                (style['primary'], style['secondary']),
                'Functions')
        self.graph_proportion_row(ax, 0.0,
                (frame, len(entries) - frame),
                ('Kept', 'Omitted'),
                (style['good'], style['secondary']),
                'Frame Pointer')
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(-0.4, 2.6)
        self.graph_render(fig, self.opts.graph_split_filename,
                GRAPH_DESCRIPTIONS['layout-split'])


    def graph_share_histogram(self, entries):
        shares = [self.percent(e['size'], e['cold']) for e in entries
                  if e['ret_end'] is not None]
        if not shares:
            self.graph_skip(self.opts.graph_histogram_filename)
            return
        buckets = list(range(0, 100, 10))
        counts = [0] * len(buckets)
        for share in shares:
            counts[min(int(share // 10), 9)] += 1
        fig, ax = self.graph_axes(xlabel='Cold Tail Share [%]', ylabel='Functions')
        self.graph_grid(ax, 'y')
        x = range(len(buckets))
        bars = ax.bar(x, counts, width=0.72, color=self.graph_value_colors(counts))
        ax.set_xticks(list(x))
        ax.set_xticklabels(["%d-%d" % (b, b + 10) for b in buckets])
        ax.margins(y=0.12)
        self.graph_bar_labels(ax, bars, total=len(shares))
        self.graph_render(fig, self.opts.graph_histogram_filename,
                GRAPH_DESCRIPTIONS['layout-histogram'])


    def graph_size_scatter(self, entries):
        points = [(e['size'], self.percent(e['size'], e['cold']))
                  for e in entries if e['ret_end'] is not None]
        if not points:
            self.graph_skip(self.opts.graph_scatter_filename)
            return
        style = self.graph_style()
        sizes = [p[0] for p in points]
        shares = [p[1] for p in points]
        fig, ax = self.graph_axes(xlabel='Function Size [Byte]',
                ylabel='Cold Tail Share [%]')
        self.graph_grid(ax, 'y')
        lo, hi = style['ramp']
        ax.scatter(sizes, shares, s=14, c=shares, cmap='plasma',
                vmin=-20, vmax=120, alpha=0.65, edgecolors='none', zorder=3)
        ax.set_xscale('log')
        ax.set_ylim(-3, 103)
        self.graph_render(fig, self.opts.graph_scatter_filename,
                GRAPH_DESCRIPTIONS['layout-scatter'])


    def show_summary(self, entries):
        total = sum(e['size'] for e in entries)
        cold = sum(e['cold'] for e in entries)
        no_ret = sum(1 for e in entries if e['ret_end'] is None)
        with_tail = sum(1 for e in entries if e['cold'] > 0)
        tail_jumps = sum(e['tail_jumps'] for e in entries)

        self.msg("Number of analyzed functions: %d\n" % (len(entries)))
        self.msg("Functions without any ret:    %d  [ %.2f%% ]\n" %
                (no_ret, self.percent(len(entries), no_ret)))
        self.msg("Functions with a cold tail:   %d  [ %.2f%% ]\n\n" %
                (with_tail, self.percent(len(entries), with_tail)))
        self.msg("Code bytes: %d\n" % (total))
        self.msg("    hot:  %8d  [ %.2f%% ]\n" %
                (total - cold, self.percent(total, total - cold)))
        self.msg("    cold: %8d  [ %.2f%% ]\n" %
                (cold, self.percent(total, cold)))
        self.msg("Conditional jumps into a cold tail: %d\n" % (tail_jumps))
        frame = sum(1 for e in entries if e['frame_pointer'])
        self.msg("Frame pointer kept (push %%rbp prologue): %d of %d  [ %.2f%% ]\n" %
                (frame, len(entries), self.percent(len(entries), frame)))


    def show_histogram(self, entries):
        shares = [self.percent(e['size'], e['cold']) for e in entries
                  if e['ret_end'] is not None]
        if not shares:
            return
        self.msg_underline("Cold Tail Share Histogram", pre_news=2, post_news=2)
        buckets = list(range(0, 100, 10))
        counts = [0] * len(buckets)
        for share in shares:
            counts[min(int(share // 10), 9)] += 1
        for bucket, cnt in zip(buckets, counts):
            self.msg("%3d-%3d%%:   %6d   [ %5.2f%% ]\n" %
                    (bucket, bucket + 10, cnt, self.percent(len(shares), cnt)))


    def show_functions(self, entries):
        top = sorted((e for e in entries if e['cold'] > 0),
                key=lambda e: e['cold'], reverse=True)[:20]
        if not top:
            return
        self.msg_underline("Functions With The Largest Cold Tails",
                pre_news=2, post_news=2)
        fmt = "%%%d.%ds: %%7d byte cold of %%7d  [ %%5.2f%%%% ]  tail jumps: %%d\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname)
        for e in top:
            self.msg(fmt % (e['name'], e['cold'], e['size'],
                     self.percent(e['size'], e['cold']), e['tail_jumps']))


    def show(self):
        entries = self.evaluate()
        self.msg_underline("Hot/Cold Layout Analysis", pre_news=2, post_news=2)
        if not entries:
            self.msg("No functions found\n")
            return
        self.show_summary(entries)
        self.show_histogram(entries)
        self.show_functions(entries)
        self.write_json('layout', self.json_data(entries))

        if self.opts.graph_map:
            self.graph_layout_map(entries)
        if self.opts.graph_split:
            self.graph_hot_cold_split(entries)
        if self.opts.graph_histogram:
            self.graph_share_histogram(entries)
        if self.opts.graph_scatter:
            self.graph_size_scatter(entries)



def check_stack_mangling_op(atom):
    # detect stack frame allocations:
    #   sub $0x210,%rsp          static allocation
    #   sub %rax,%rsp            dynamic allocation (VLA, alloca)
    #   add $-0x80,%rsp          smart GCC: adding a negative imm8 is
    #                            shorter encoded than the sub counterpart
    if atom.type != BinaryAtom.TYPE_2:
        return None
    if atom.dst not in ('%rsp', '%esp'):
        return None
    if atom.mnemonic not in ('sub', 'subq', 'subl', 'add', 'addq', 'addl'):
        return None

    if atom.src.startswith('%'):
        retobj = RetObj(RetObj.DYNAMIC)
        retobj.val = 0
        retobj.register = atom.src
        return retobj

    if not atom.src.startswith('$'):
        # memory operand, no stack frame handling
        return None

    val = int(atom.src[1:], 0)
    if atom.mnemonic.startswith('add'):
        val = -val
    if val <= 0:
        # stack release, not an allocation
        return None
    retobj = RetObj(RetObj.STATIC)
    retobj.val = val
    return retobj


class StackAnalyzer(Common):

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.db = dict()
        self.all_function_db = dict()
        self.parse_local_options()


    GRAPHS = [
        ('histogram', 'stack-histogram.png', 'stack allocation distribution'),
        ('allocation', 'stack-allocation.png', 'share of functions with stack usage'),
        ('sizes', 'stack-sizes.png', 'static allocation size spectrum'),
    ]

    def parse_local_options(self):
        parser = module_parser("stack",
                "Stack usage: static and dynamic allocations per function.")
        add_graph_arguments(parser, StackAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, StackAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.output()


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        if context.function_name not in self.all_function_db:
            self.all_function_db[context.function_name] = True
        if context.function_name in self.db:
            func_db = self.db[context.function_name]
        else:
            func_db = dict()
            func_db['stack-usage-no'] = 0
        ret = check_stack_mangling_op(atom)
        if not ret:
            return
        # add or re-add to global database
        self.db[context.function_name] = func_db
        func_db['stack-usage-no'] += 1
        label = 'stack-usage-%d' % (func_db['stack-usage-no'])
        func_db[label] = ret.val


    def percent(self, i, j):
        if j == 0:
            return 0.0
        return (float(j) / float(i)) * 100.0


    def json_data(self, sorted_data, no_functions):
        functions = []
        for name, static, nested in sorted_data:
            entry = { 'name': name, 'static': static }
            if nested.strip() and nested.strip() != '-':
                entry['multi-level'] = nested.strip()
            functions.append(entry)
        histogram = dict()
        for i in range(3, 14):
            histogram[str(2 ** i)] = 0
        for name, static, nested in sorted_data:
            if static == 0:
                continue
            for i in range(3, 14):
                if static <= 2 ** i:
                    histogram[str(2 ** i)] += 1
                    break
        return {
            'functions-analyzed': no_functions,
            'functions-with-stack': len(self.db),
            'functions-without-stack': no_functions - len(self.db),
            'histogram': histogram,
            'functions': functions,
        }


    def graph_bucket_histogram(self, d, overall):
        style = self.graph_style()
        buckets = [2 ** i for i in range(3, 14)]
        counts = [d[b] for b in buckets]
        fig, ax = self.graph_axes(xlabel='Stack Allocation [Byte]', ylabel='Functions')
        self.graph_grid(ax, 'y')
        x = range(len(buckets))
        bars = ax.bar(x, counts, width=0.72, color=self.graph_value_colors(counts))
        ax.set_xticks(list(x))
        ax.set_xticklabels(["<= %d" % (b) for b in buckets], rotation=45, ha='right')
        ax.margins(y=0.10)
        self.graph_bar_labels(ax, bars, total=overall)
        self.graph_render(fig, self.opts.graph_histogram_filename,
                GRAPH_DESCRIPTIONS['stack-histogram'])


    def graph_allocation_sizes(self, sorted_data):
        # ranking single functions is pointless when dozens share the
        # same allocation size (PATH_MAX buffers and the like), show
        # how many functions allocate which exact amount instead
        sizes = dict()
        for data in sorted_data:
            if data[1] <= 0:
                continue
            sizes[data[1]] = sizes.get(data[1], 0) + 1
        if not sizes:
            self.graph_skip(self.opts.graph_sizes_filename)
            return
        style = self.graph_style()
        entries = sorted(sizes.items(), reverse=True)[:15]
        labels = ["%d Byte" % (size) for size, cnt in entries]
        counts = [cnt for size, cnt in entries]
        total = sum(sizes.values())
        fig, ax = self.graph_axes(xlabel='Functions With This Static Allocation')
        self.graph_grid(ax, 'x')
        y = range(len(labels))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(labels)
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True, total=total)
        self.graph_render(fig, self.opts.graph_sizes_filename,
                GRAPH_DESCRIPTIONS['stack-sizes'])


    def output_bucket_historgram(self, sorted_data, overall):
        sys.stdout.write("Stack Usage Histogram:\n")
        d = dict()
        for i in range(3, 14):
            exp = 2 ** i
            d[exp] = 0

        for data in sorted_data:
            if data[1] == 0:
                continue
            for i in range(3, 14):
                exp = 2 ** i
                if data[1] <= exp:
                    d[exp] += 1
                    break

        for i in range(3, 14):
            exp = 2 ** i
            percent = self.percent(overall, d[exp])
            sys.stdout.write("%-5d %6d    (%5.1f%% )\n" % (exp, d[exp], percent))
        sys.stdout.write("\n")

        if self.opts.graph_histogram:
            self.graph_bucket_histogram(d, overall)


    def graph_with_vs_without(self, no_functions_with, no_functions_without):
        style = self.graph_style()
        fig, ax = self.graph_axes(figsize=(8.0, 1.8))
        ax.set_axis_off()
        self.graph_proportion_row(ax, 0.0,
                (no_functions_with, no_functions_without),
                ('With Stack Allocation', 'Without'),
                (style['primary'], style['secondary']),
                'Stack Allocation per Function')
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(-0.4, 0.7)
        self.graph_render(fig, self.opts.graph_allocation_filename,
                GRAPH_DESCRIPTIONS['stack-allocation'])


    def output_with_vs_without(self, no_functions, no_functions_with, no_functions_without):
        percent_w_stack = self.percent(no_functions, no_functions_with)
        sys.stdout.write("Function with stack utilization: %5d   (%4.0f%% )\n" %
                (no_functions_with, percent_w_stack))
        percent_wo_stack = self.percent(no_functions, no_functions_without)
        sys.stdout.write("Function w/o stack utilization:  %5d   (%4.0f%% )\n" %
                (no_functions_without, percent_wo_stack))
        sys.stdout.write("\n")

        if self.opts.graph_allocation:
            self.graph_with_vs_without(no_functions_with, no_functions_without)


    def output(self):
        no_functions = len(self.all_function_db)
        function_with_stack = len(self.db)
        function_without_stack = no_functions - function_with_stack

        self.output_with_vs_without(no_functions, function_with_stack, function_without_stack)

        # We first sort the entries here, this is somewhat not
        # Pythonlikelambda but opens the possibility to do a more
        # advanced sorting
        sorted_data = []
        for function_name, value in self.db.items():
            cnt =  self.db[function_name]['stack-usage-no']
            nested = ""
            for i in range(cnt - 1):
                label = 'stack-usage-%d' % (i + 2)
                d = self.db[function_name][label]
                if d == 0:
                    nested += "Dynamic "
                else:
                    nested += str(d) + " "
            if nested == '':
                nested = "-"
            sorted_data.append([function_name, int(self.db[function_name]['stack-usage-1']), nested])

        sorted_data.sort(reverse=True, key=lambda d: d[1])
        self.output_bucket_historgram(sorted_data, function_with_stack)
        self.write_json('stack', self.json_data(sorted_data, no_functions))
        if self.opts.graph_sizes:
            self.graph_allocation_sizes(sorted_data)
        sys.stdout.write("%-40.40s %5.5s   %25.25s\n" % ("Function Name", "Byte", "Multi Level Allocation"))
        for data in sorted_data:
            if data[1] == 0:
                sys.stdout.write("%-40.40s Dynamic   %-20.20s\n" % (data[0], data[2]))
            else:
                sys.stdout.write("%-40.40s %5.d      %-20.20s\n" % (data[0], data[1], data[2]))




class AtomicAnalyzer(Common):

    FENCES = ('mfence', 'lfence', 'sfence')

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.db = dict()
        self.insn_cnt = 0
        self.cas = 0
        self.xadd = 0
        self.xchg = 0
        self.rmw = 0
        self.fences = dict((f, 0) for f in AtomicAnalyzer.FENCES)
        self.fence_idiom = 0
        self.pauses = 0
        self.spin_loops = 0
        self.cas_loops = 0
        self.irq_toggle = 0
        self.monitor_wait = 0
        self.strlen_longest_funcname = 10
        # per function state for the loop detection
        self.current_function = None
        self.pause_addrs = []
        self.cas_addrs = []


    GRAPHS = [
        ('operations', 'atomic-operations.png', 'atomic operation breakdown'),
        ('functions', 'atomic-functions.png', 'functions with the most atomics'),
    ]

    def parse_local_options(self):
        parser = module_parser("atomic",
                "Synchronization: locked operations, fences and spin loops.")
        add_graph_arguments(parser, AtomicAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, AtomicAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def function_db(self, context):
        func_id = "%s:%s" % (context.function_name, context.function_start_address)
        if func_id not in self.db:
            self.db[func_id] = { 'atomics': 0, 'cas': 0, 'rmw': 0,
                                 'fences': 0, 'spin-loops': 0 }
            self.strlen_longest_funcname = max(len(context.function_name),
                                               self.strlen_longest_funcname)
        return self.db[func_id]


    def is_memory_operand(self, operand):
        if operand is None:
            return False
        # AT&T: everything but a register or an immediate references memory
        return not operand.startswith('%') and not operand.startswith('$')


    def process_loops(self, context, atom):
        # a backward local jump over a pause is a spin wait loop, a
        # backward local jump over a cmpxchg is a CAS retry loop
        if not atom.is_jump or atom.jmp_addr is None:
            return
        if atom.jmp_addr > atom.addr:
            return
        if atom.jmp_addr < context.function_start_address:
            return

        spins = [a for a in self.pause_addrs if atom.jmp_addr <= a <= atom.addr]
        if spins:
            self.spin_loops += 1
            self.function_db(context)['spin-loops'] += 1
            self.pause_addrs = [a for a in self.pause_addrs if a not in spins]

        cas = [a for a in self.cas_addrs if atom.jmp_addr <= a <= atom.addr]
        if cas:
            self.cas_loops += 1
            self.cas_addrs = [a for a in self.cas_addrs if a not in cas]


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        self.insn_cnt += 1
        if context.function_start_address != self.current_function:
            self.current_function = context.function_start_address
            self.pause_addrs = []
            self.cas_addrs = []

        self.process_loops(context, atom)

        tokens = atom.mnemonic.split()
        base = re.sub(r'[bwlq]$', '', tokens[-1])

        if base == 'pause':
            self.pauses += 1
            self.pause_addrs.append(atom.addr)
            return
        if base in AtomicAnalyzer.FENCES:
            self.fences[base] += 1
            self.function_db(context)['fences'] += 1
            return
        if base in ('cli', 'sti'):
            self.irq_toggle += 1
            return
        if base in ('monitor', 'mwait', 'umonitor', 'umwait', 'tpause'):
            self.monitor_wait += 1
            return

        # xchg with a memory operand is implicitly locked
        locked = tokens[0] == 'lock'
        implicit = base == 'xchg' and (self.is_memory_operand(atom.src) or
                                       self.is_memory_operand(atom.dst))
        if not locked and not implicit:
            return

        fdb = self.function_db(context)
        fdb['atomics'] += 1
        if base.startswith('cmpxchg'):
            self.cas += 1
            fdb['cas'] += 1
            self.cas_addrs.append(atom.addr)
        elif base == 'xadd':
            self.xadd += 1
            fdb['rmw'] += 1
        elif base == 'xchg':
            self.xchg += 1
            fdb['rmw'] += 1
        elif base == 'or' and atom.src == '$0':
            # lock orq $0x0,(%rsp): GCC idiom for a sequential
            # consistency fence, cheaper than mfence
            self.fence_idiom += 1
            fdb['atomics'] -= 1
            fdb['fences'] += 1
        else:
            self.rmw += 1
            fdb['rmw'] += 1


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def json_data(self):
        functions = dict()
        for func_id, value in self.db.items():
            functions[func_id.split(':')[0]] = value
        return {
            'instructions': self.insn_cnt,
            'compare-and-swap': self.cas,
            'fetch-and-add': self.xadd,
            'atomic-swap': self.xchg,
            'locked-rmw': self.rmw,
            'fences': self.fences,
            'fence-idiom': self.fence_idiom,
            'pause-hints': self.pauses,
            'spin-loops': self.spin_loops,
            'cas-retry-loops': self.cas_loops,
            'irq-toggle': self.irq_toggle,
            'monitor-wait': self.monitor_wait,
            'functions': functions,
        }


    def graph_operation_breakdown(self):
        style = self.graph_style()
        entries = [
            ('compare-and-swap', self.cas),
            ('fetch-and-add', self.xadd),
            ('atomic swap', self.xchg),
            ('other locked RMW', self.rmw),
            ('fences', sum(self.fences.values()) + self.fence_idiom),
            ('pause hints', self.pauses),
        ]
        names = [name for name, cnt in entries]
        counts = [cnt for name, cnt in entries]
        if sum(counts) == 0:
            self.graph_skip(self.opts.graph_operations_filename)
            return
        fig, ax = self.graph_axes(xlabel='Operations', figsize=(8.0, 3.4))
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.08)
        self.graph_bar_labels(ax, bars, horizontal=True, total=sum(counts))
        self.graph_render(fig, self.opts.graph_operations_filename,
                GRAPH_DESCRIPTIONS['atomic-operations'])


    def graph_top_functions(self):
        if not self.db:
            self.graph_skip(self.opts.graph_functions_filename)
            return
        style = self.graph_style()
        entries = sorted(self.db.items(),
                key=lambda item: item[1]['atomics'] + item[1]['fences'],
                reverse=True)[:20]
        names = [func_id.split(':')[0] for func_id, value in entries]
        counts = [value['atomics'] + value['fences'] for func_id, value in entries]
        fig, ax = self.graph_axes(xlabel='Atomic Operations and Fences')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.08)
        self.graph_bar_labels(ax, bars, horizontal=True, total=sum(counts))
        self.graph_render(fig, self.opts.graph_functions_filename,
                GRAPH_DESCRIPTIONS['atomic-functions'])


    def show_functions(self):
        if not self.db:
            return
        self.msg_underline("Functions", pre_news=2, post_news=2)
        fmt = "%%%d.%ds: %%3d atomics  [cas: %%d, rmw: %%d, fences: %%d, spin-loops: %%d]\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname)
        entries = sorted(self.db.items(),
                key=lambda item: item[1]['atomics'] + item[1]['fences'],
                reverse=True)
        for func_id, value in entries:
            self.msg(fmt % (func_id.split(':')[0], value['atomics'],
                     value['cas'], value['rmw'], value['fences'],
                     value['spin-loops']))


    def show(self):
        locked = self.cas + self.xadd + self.xchg + self.rmw
        fences = sum(self.fences.values())

        self.msg_underline("Atomic and Lock Analysis", pre_news=2, post_news=2)
        self.msg("Number of analyzed instructions: %d\n\n" % (self.insn_cnt))
        self.msg("Locked operations:  %6d  [ %.3f%% of all instructions ]\n" %
                (locked, self.percent(self.insn_cnt, locked)))
        self.msg("    compare-and-swap:      %6d\n" % (self.cas))
        self.msg("    fetch-and-add:         %6d\n" % (self.xadd))
        self.msg("    atomic swap (xchg):    %6d\n" % (self.xchg))
        self.msg("    other locked RMW:      %6d\n" % (self.rmw))
        self.msg("Memory fences:      %6d\n" %
                (fences + self.fence_idiom))
        for fence in AtomicAnalyzer.FENCES:
            self.msg("    %s:                %6d\n" % (fence, self.fences[fence]))
        self.msg("    fence idiom (lock or): %6d\n" % (self.fence_idiom))
        self.msg("Spin wait hints (pause):   %6d\n" % (self.pauses))
        self.msg("Spin loops:                %6d\n" % (self.spin_loops))
        self.msg("CAS retry loops:           %6d\n" % (self.cas_loops))
        self.msg("Interrupt toggle (cli/sti):%6d\n" % (self.irq_toggle))
        self.msg("Monitor/wait:              %6d\n" % (self.monitor_wait))

        self.show_functions()
        self.write_json('atomic', self.json_data())

        if self.opts.graph_operations:
            self.graph_operation_breakdown()
        if self.opts.graph_functions:
            self.graph_top_functions()



class IdiomAnalyzer(Common):

    GRAPHS = [
        ('pairs', 'idiom-pairs.png', 'most frequent instruction pairs'),
        ('matrix', 'idiom-matrix.png', 'instruction transition matrix'),
        ('flow', 'idiom-flow.png', 'what follows each instruction'),
        ('trigrams', 'idiom-trigrams.png', 'most frequent instruction triples'),
    ]

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.mnemonics = dict()
        self.pairs = dict()
        self.triples = dict()
        self.successors = dict()
        self.insn_cnt = 0
        self.current_function = None
        self.window = []


    def parse_local_options(self):
        parser = module_parser("idiom",
                "Instruction idioms: which instruction follows which.")
        add_graph_arguments(parser, IdiomAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, IdiomAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        # sequences do not cross function boundaries
        if context.function_start_address != self.current_function:
            self.current_function = context.function_start_address
            del self.window[:]

        base = re.sub(r'[bwlq]$', '', atom.mnemonic.split()[-1])
        self.insn_cnt += 1
        self.mnemonics[base] = self.mnemonics.get(base, 0) + 1
        if self.window:
            prev = self.window[-1]
            pair = (prev, base)
            self.pairs[pair] = self.pairs.get(pair, 0) + 1
            successors = self.successors.setdefault(prev, dict())
            successors[base] = successors.get(base, 0) + 1
        if len(self.window) >= 2:
            triple = (self.window[-2], self.window[-1], base)
            self.triples[triple] = self.triples.get(triple, 0) + 1
        self.window.append(base)
        del self.window[:-2]


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def top_mnemonics(self, n):
        return [name for name, cnt in sorted(self.mnemonics.items(),
                key=lambda item: item[1], reverse=True)[:n]]


    def json_data(self):
        pairs = [[a, b, cnt] for (a, b), cnt in sorted(self.pairs.items(),
                 key=lambda item: item[1], reverse=True)]
        triples = [[a, b, c, cnt] for (a, b, c), cnt
                   in sorted(self.triples.items(),
                   key=lambda item: item[1], reverse=True)]
        return {
            'instructions': self.insn_cnt,
            'mnemonics': self.mnemonics,
            'pairs': pairs,
            'triples': triples,
        }


    def graph_pair_ranking(self):
        if not self.pairs:
            self.graph_skip(self.opts.graph_pairs_filename)
            return
        total = sum(self.pairs.values())
        entries = sorted(self.pairs.items(), key=lambda item: item[1],
                reverse=True)[:20]
        names = ["%s -> %s" % pair for pair, cnt in entries]
        counts = [cnt for pair, cnt in entries]
        fig, ax = self.graph_axes(xlabel='Occurrences')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names, family='monospace')
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True, total=total)
        self.graph_render(fig, self.opts.graph_pairs_filename,
                GRAPH_DESCRIPTIONS['idiom-pairs'])


    def graph_triple_ranking(self):
        if not self.triples:
            self.graph_skip(self.opts.graph_trigrams_filename)
            return
        total = sum(self.triples.values())
        entries = sorted(self.triples.items(), key=lambda item: item[1],
                reverse=True)[:15]
        names = ["%s -> %s -> %s" % triple for triple, cnt in entries]
        counts = [cnt for triple, cnt in entries]
        fig, ax = self.graph_axes(xlabel='Occurrences')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names, family='monospace')
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True, total=total)
        self.graph_render(fig, self.opts.graph_trigrams_filename,
                GRAPH_DESCRIPTIONS['idiom-trigrams'])


    def graph_successor_flow(self):
        top = self.top_mnemonics(12)
        if not top:
            self.graph_skip(self.opts.graph_flow_filename)
            return
        style = self.graph_style()
        cmap = matplotlib.colormaps['plasma']
        lo, hi = style['ramp']
        fig, ax = self.graph_axes(xlabel='Share of the Next Instruction [%]',
                figsize=(9.0, 5.5))
        rows = list(reversed(top))   # most frequent on top
        for i, current in enumerate(rows):
            successors = self.successors.get(current, dict())
            total = sum(successors.values())
            if total == 0:
                continue
            entries = sorted(successors.items(), key=lambda kv: kv[1],
                    reverse=True)
            head = entries[:6]
            rest = sum(c for name, c in entries[6:])
            segments = list(head)
            if rest > 0:
                segments.append(('other', rest))
            left = 0.0
            for rank, (name, cnt) in enumerate(segments):
                frac = cnt / float(total)
                shade = hi - (hi - lo) * (1.0 - rank / max(len(segments) - 1, 1))
                color = cmap(shade)
                ax.barh(i, frac, left=left, height=0.72, color=color,
                        zorder=2)
                if frac > 0.05:
                    # dark text on the light (yellow) end, light on the deep end
                    ink = '#1a1a1a' if shade > 0.55 else '#f2f2f2'
                    ax.text(left + frac / 2, i,
                            '%s\n%.0f%%' % (name, frac * 100.0),
                            ha='center', va='center', fontsize=7,
                            family='monospace', color=ink, zorder=3)
                left += frac
        ax.set_yticks(range(len(rows)))
        ax.set_yticklabels(rows, family='monospace')
        ax.set_xlim(0.0, 1.0)
        ax.set_xticks([0.0, 0.25, 0.5, 0.75, 1.0])
        ax.set_xticklabels(['0', '25', '50', '75', '100'])
        ax.set_ylim(-0.6, len(rows) - 0.4)
        self.graph_render(fig, self.opts.graph_flow_filename,
                GRAPH_DESCRIPTIONS['idiom-flow'])


    def graph_transition_matrix(self):
        top = self.top_mnemonics(12)
        if not top:
            self.graph_skip(self.opts.graph_matrix_filename)
            return
        style = self.graph_style()
        matrix = []
        for current in top:
            successors = self.successors.get(current, dict())
            total = sum(successors.values())
            row = []
            for nxt in top:
                row.append(self.percent(total, successors.get(nxt, 0)))
            matrix.append(row)

        fig, ax = self.graph_axes(xlabel='Next Instruction',
                ylabel='Current Instruction', figsize=(8.0, 6.4))
        image = ax.imshow(matrix, cmap='plasma', vmin=0.0, aspect='auto',
                interpolation='nearest')
        ax.set_xticks(range(len(top)))
        ax.set_xticklabels(top, family='monospace', rotation=45, ha='right')
        ax.set_yticks(range(len(top)))
        ax.set_yticklabels(top, family='monospace')
        vmax = max(max(row) for row in matrix) or 1.0
        for i, row in enumerate(matrix):
            for j, val in enumerate(row):
                if val < 3.0:
                    continue
                color = '#1a1a1a' if val > 0.55 * vmax else '#f0f0f0'
                ax.text(j, i, "%.0f" % (val), ha='center', va='center',
                        fontsize=7, color=color)
        bar = fig.colorbar(image, ax=ax, shrink=0.8)
        bar.set_label('P(Next | Current) [%]', color=style['ink'], fontsize=9)
        bar.ax.tick_params(colors=style['frame'], labelcolor=style['ink'],
                labelsize=8)
        bar.outline.set_edgecolor(style['frame'])
        self.graph_render(fig, self.opts.graph_matrix_filename,
                GRAPH_DESCRIPTIONS['idiom-matrix'])


    def show(self):
        self.msg_underline("Instruction Idiom Analysis", pre_news=2, post_news=2)
        self.msg("Number of analyzed instructions: %d\n" % (self.insn_cnt))
        self.msg("Distinct mnemonics (suffix normalized): %d\n" %
                (len(self.mnemonics)))
        self.msg("Distinct instruction pairs: %d\n" % (len(self.pairs)))

        total_pairs = sum(self.pairs.values())
        self.msg_underline("Top Instruction Pairs", pre_news=2, post_news=2)
        for pair, cnt in sorted(self.pairs.items(), key=lambda item: item[1],
                reverse=True)[:25]:
            self.msg("%8d  [ %5.2f%% ]   %-8s -> %s\n" %
                    (cnt, self.percent(total_pairs, cnt), pair[0], pair[1]))

        total_triples = sum(self.triples.values())
        self.msg_underline("Top Instruction Triples", pre_news=2, post_news=2)
        for triple, cnt in sorted(self.triples.items(), key=lambda item: item[1],
                reverse=True)[:15]:
            self.msg("%8d  [ %5.2f%% ]   %-8s -> %-8s -> %s\n" %
                    (cnt, self.percent(total_triples, cnt),
                     triple[0], triple[1], triple[2]))

        self.msg_underline("Preferred Successors", pre_news=2, post_news=2)
        for current in self.top_mnemonics(12):
            successors = self.successors.get(current, dict())
            total = sum(successors.values())
            if total == 0:
                continue
            top3 = sorted(successors.items(), key=lambda item: item[1],
                    reverse=True)[:3]
            parts = ", ".join("%s %.1f%%" % (name, self.percent(total, cnt))
                              for name, cnt in top3)
            self.msg("%-8s -> %s\n" % (current, parts))

        self.write_json('idiom', self.json_data())

        if self.opts.graph_pairs:
            self.graph_pair_ranking()
        if self.opts.graph_matrix:
            self.graph_transition_matrix()
        if self.opts.graph_flow:
            self.graph_successor_flow()
        if self.opts.graph_trigrams:
            self.graph_triple_ranking()



class CallAnalyzer(Common):

    GRAPHS = [
        ('called', 'call-called.png', 'most called functions'),
        ('fanout', 'call-fanout.png', 'calls per function distribution'),
        ('kinds', 'call-kinds.png', 'direct, external and indirect call shares'),
    ]

    FANOUT_BUCKETS = [(0, '0 (Leaf)'), (1, '1'), (2, '2'), (4, '3-4'),
                      (8, '5-8'), (16, '9-16'), (32, '17-32'),
                      (sys.maxsize, '33+')]

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.db = dict()
        self.functions = dict()
        self.strlen_longest_funcname = 10


    def parse_local_options(self):
        parser = module_parser("call",
                "Call structure: who calls whom, directly or indirectly.")
        add_graph_arguments(parser, CallAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, CallAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def function_db(self, context):
        func_id = "%s:%s" % (context.function_name, context.function_start_address)
        if func_id not in self.db:
            self.db[func_id] = {
                'name': context.function_name,
                'start': context.function_start_address,
                'size': context.function_size,
                'direct': 0,
                'indirect': 0,
                'tail': 0,
                'recursive': 0,
                'targets': [],
            }
            self.functions[context.function_start_address] = context.function_name
            self.strlen_longest_funcname = max(len(context.function_name),
                                               self.strlen_longest_funcname)
        return self.db[func_id]


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        fdb = self.function_db(context)
        base = re.sub(r'[bwlq]$', '', atom.mnemonic.split()[-1])
        if base == 'call':
            if atom.jmp_addr is None:
                # call through a register or memory pointer
                fdb['indirect'] += 1
                return
            fdb['direct'] += 1
            fdb['targets'].append(atom.jmp_addr)
            if atom.jmp_addr == fdb['start']:
                fdb['recursive'] += 1
        elif base == 'jmp' and atom.jmp_addr is not None:
            if not fdb['start'] <= atom.jmp_addr < fdb['start'] + fdb['size']:
                # jump leaving the function: a tail call
                fdb['tail'] += 1
                fdb['targets'].append(atom.jmp_addr)


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def fan_in(self):
        internal = dict()
        external = 0
        for fdb in self.db.values():
            for target in fdb['targets']:
                name = self.functions.get(target)
                if name is None:
                    external += 1
                else:
                    internal[name] = internal.get(name, 0) + 1
        return internal, external


    def fanout_histogram(self):
        counts = [0] * len(CallAnalyzer.FANOUT_BUCKETS)
        for fdb in self.db.values():
            sites = fdb['direct'] + fdb['indirect'] + fdb['tail']
            for i, (limit, label) in enumerate(CallAnalyzer.FANOUT_BUCKETS):
                if sites <= limit:
                    counts[i] += 1
                    break
        return counts


    def json_data(self, internal, external, leafs):
        functions = []
        for f in sorted(self.db.values(),
                key=lambda f: f['direct'] + f['indirect'], reverse=True):
            functions.append({
                'name': f['name'],
                'direct': f['direct'],
                'indirect': f['indirect'],
                'tail': f['tail'],
                'recursive': f['recursive'],
            })
        return {
            'functions-analyzed': len(self.db),
            'call-sites-direct-internal': sum(internal.values()),
            'call-sites-direct-external': external,
            'call-sites-indirect': sum(f['indirect'] for f in self.db.values()),
            'tail-calls': sum(f['tail'] for f in self.db.values()),
            'leaf-functions': leafs,
            'fan-in': internal,
            'functions': functions,
        }


    def graph_most_called(self, internal):
        if not internal:
            self.graph_skip(self.opts.graph_called_filename)
            return
        total = sum(internal.values())
        entries = sorted(internal.items(), key=lambda item: item[1],
                reverse=True)[:20]
        names = [name for name, cnt in entries]
        counts = [cnt for name, cnt in entries]
        fig, ax = self.graph_axes(xlabel='Call Sites')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True, total=total)
        self.graph_render(fig, self.opts.graph_called_filename,
                GRAPH_DESCRIPTIONS['call-called'])


    def graph_fanout_histogram(self):
        counts = self.fanout_histogram()
        if sum(counts) == 0:
            self.graph_skip(self.opts.graph_fanout_filename)
            return
        labels = [label for limit, label in CallAnalyzer.FANOUT_BUCKETS]
        fig, ax = self.graph_axes(xlabel='Call Sites per Function',
                ylabel='Functions')
        self.graph_grid(ax, 'y')
        x = range(len(labels))
        bars = ax.bar(x, counts, width=0.72, color=self.graph_value_colors(counts))
        ax.set_xticks(list(x))
        ax.set_xticklabels(labels)
        ax.margins(y=0.12)
        self.graph_bar_labels(ax, bars, total=sum(counts))
        self.graph_render(fig, self.opts.graph_fanout_filename,
                GRAPH_DESCRIPTIONS['call-fanout'])


    def graph_call_kinds(self, internal_sites, external, indirect, leafs):
        style = self.graph_style()
        fig, ax = self.graph_axes(figsize=(8.0, 2.4))
        ax.set_axis_off()
        self.graph_proportion_row(ax, 1.0,
                (internal_sites, external, indirect),
                ('Direct Internal', 'External', 'Indirect'),
                (style['primary'], style['secondary'], style['good']),
                'Call Kinds')
        self.graph_proportion_row(ax, 0.0,
                (leafs, len(self.db) - leafs),
                ('Leaf', 'Calling'),
                (style['secondary'], style['primary']),
                'Functions')
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(-0.4, 1.6)
        self.graph_render(fig, self.opts.graph_kinds_filename,
                GRAPH_DESCRIPTIONS['call-kinds'])


    def show(self):
        internal, external = self.fan_in()
        direct = sum(f['direct'] for f in self.db.values())
        indirect = sum(f['indirect'] for f in self.db.values())
        tail = sum(f['tail'] for f in self.db.values())
        recursive = [f for f in self.db.values() if f['recursive']]
        leafs = sum(1 for f in self.db.values()
                    if f['direct'] + f['indirect'] + f['tail'] == 0)
        sites = direct + indirect
        internal_sites = sum(internal.values())

        self.msg_underline("Call Structure Analysis", pre_news=2, post_news=2)
        self.msg("Number of analyzed functions: %d\n" % (len(self.db)))
        self.msg("Call sites: %d\n" % (sites))
        self.msg("    direct, internal target:  %6d  [ %5.2f%% ]\n" %
                (internal_sites, self.percent(sites, internal_sites)))
        self.msg("    direct, external target:  %6d  [ %5.2f%% ]\n" %
                (external, self.percent(sites, external)))
        self.msg("    indirect (pointer):       %6d  [ %5.2f%% ]\n" %
                (indirect, self.percent(sites, indirect)))
        self.msg("Tail calls (jmp out of the function): %d\n" % (tail))
        self.msg("Directly recursive functions: %d\n" % (len(recursive)))
        self.msg("Leaf functions: %d of %d  [ %5.2f%% ]\n" %
                (leafs, len(self.db), self.percent(len(self.db), leafs)))

        self.msg_underline("Most Called Functions", pre_news=2, post_news=2)
        fmt = "%%%d.%ds: %%6d call sites\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname)
        for name, cnt in sorted(internal.items(), key=lambda item: item[1],
                reverse=True)[:20]:
            self.msg(fmt % (name, cnt))

        self.msg_underline("Functions With The Most Call Sites", pre_news=2,
                post_news=2)
        fmt = "%%%d.%ds: %%5d call sites  [direct: %%d, indirect: %%d]\n" % \
                (self.strlen_longest_funcname, self.strlen_longest_funcname)
        entries = sorted(self.db.values(),
                key=lambda f: f['direct'] + f['indirect'], reverse=True)[:15]
        for f in entries:
            self.msg(fmt % (f['name'], f['direct'] + f['indirect'],
                     f['direct'], f['indirect']))

        self.write_json('call', self.json_data(internal, external, leafs))

        if self.opts.graph_called:
            self.graph_most_called(internal)
        if self.opts.graph_fanout:
            self.graph_fanout_histogram()
        if self.opts.graph_kinds:
            self.graph_call_kinds(internal_sites, external, indirect, leafs)



class HardeningAnalyzer(Common):

    GRAPHS = [
        ('card', 'hardening-card.png',
         'the full mitigation status of the binary'),
        ('coverage', 'hardening-coverage.png', 'CET and stack protector coverage'),
        ('unprotected', 'hardening-unprotected.png',
         'largest functions without a stack canary'),
    ]

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.db = dict()
        self.lfences = 0
        self.strlen_longest_funcname = 10


    def parse_local_options(self):
        parser = module_parser("hardening",
                "Mitigation coverage: CET, stack protector, speculation barriers.")
        add_graph_arguments(parser, HardeningAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, HardeningAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def function_db(self, context):
        func_id = "%s:%s" % (context.function_name, context.function_start_address)
        if func_id not in self.db:
            self.db[func_id] = {
                'name': context.function_name,
                'size': context.function_size,
                'first': None,
                'canary': False,
                'thunk': context.function_name.startswith('__x86_indirect_thunk'),
            }
            self.strlen_longest_funcname = max(len(context.function_name),
                                               self.strlen_longest_funcname)
        return self.db[func_id]


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        fdb = self.function_db(context)
        base = atom.mnemonic.split()[-1]
        if fdb['first'] is None:
            fdb['first'] = base
        if base == 'lfence':
            self.lfences += 1
        # the stack protector loads the canary from the TLS block
        if not fdb['canary'] and '%fs:0x28' in atom.line:
            fdb['canary'] = True


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def coverage(self):
        endbr = sum(1 for f in self.db.values()
                    if f['first'] in ('endbr64', 'endbr32'))
        canary = sum(1 for f in self.db.values() if f['canary'])
        thunks = sum(1 for f in self.db.values() if f['thunk'])
        return endbr, canary, thunks


    def elf_mitigations(self):
        # the load-time mitigations live in the ELF headers, not in the
        # instruction stream: read them straight with pyelftools
        m = {'pie': False, 'nx': True, 'relro': 'none', 'runpath': None,
             'fortify': False}
        try:
            with open(self.opts.filename, 'rb') as f:
                elf = ELFFile(f)
                etype = elf.header['e_type']
                has_interp = False
                gnu_stack = None
                relro_seg = False
                for seg in elf.iter_segments():
                    ptype = seg['p_type']
                    if ptype == 'PT_INTERP':
                        has_interp = True
                    elif ptype == 'PT_GNU_STACK':
                        gnu_stack = seg
                    elif ptype == 'PT_GNU_RELRO':
                        relro_seg = True
                # a PIE executable is a shared object with an interpreter;
                # an ET_EXEC loads at a fixed address
                m['pie'] = (etype == 'ET_DYN' and has_interp)
                if gnu_stack is not None:
                    m['nx'] = not (gnu_stack['p_flags'] & 0x1)  # PF_X
                bind_now = False
                dyn = elf.get_section_by_name('.dynamic')
                if dyn is not None:
                    for tag in dyn.iter_tags():
                        t = tag.entry.d_tag
                        if t == 'DT_BIND_NOW':
                            bind_now = True
                        elif t == 'DT_FLAGS' and (tag.entry.d_val & 0x8):
                            bind_now = True  # DF_BIND_NOW
                        elif t == 'DT_FLAGS_1' and (tag.entry.d_val & 0x1):
                            bind_now = True  # DF_1_NOW
                        elif t == 'DT_RUNPATH':
                            m['runpath'] = getattr(tag, 'runpath', '')
                        elif t == 'DT_RPATH':
                            m['runpath'] = getattr(tag, 'rpath', '')
                if relro_seg and bind_now:
                    m['relro'] = 'full'
                elif relro_seg:
                    m['relro'] = 'partial'
                dynsym = elf.get_section_by_name('.dynsym')
                if dynsym is not None:
                    for sym in dynsym.iter_symbols():
                        if sym.name.endswith('_chk'):
                            m['fortify'] = True
                            break
        except Exception as exc:
            self.err("could not read ELF mitigations: %s\n" % (exc))
        return m


    def json_data(self):
        endbr, canary, thunks = self.coverage()
        functions = []
        for f in sorted(self.db.values(), key=lambda f: f['size'],
                reverse=True):
            functions.append({
                'name': f['name'],
                'size': f['size'],
                'endbr': f['first'] in ('endbr64', 'endbr32'),
                'canary': f['canary'],
            })
        elf = getattr(self, 'elf', None) or self.elf_mitigations()
        return {
            'functions-analyzed': len(self.db),
            'endbr-functions': endbr,
            'canary-functions': canary,
            'retpoline-thunks': thunks,
            'lfences': self.lfences,
            'pie': elf['pie'],
            'nx': elf['nx'],
            'relro': elf['relro'],
            'runpath': elf['runpath'],
            'fortify': elf['fortify'],
            'functions': functions,
        }


    def graph_hardening_card(self):
        style = self.graph_style()
        if not hasattr(self, 'elf'):
            self.elf = self.elf_mitigations()
        e = self.elf
        endbr, canary, thunks = self.coverage()
        n = len(self.db)
        endbr_pct = self.percent(n, endbr)

        good, bad, warn = style['good'], style['bad'], style['secondary']
        # one row per layer: (name, status verdict color, detail text)
        cet = (good if endbr_pct >= 90.0 else warn if endbr > 0 else bad)
        rows = [
            ('PIE / ASLR', good if e['pie'] else bad,
             'position independent' if e['pie'] else 'no, fixed load address'),
            ('NX', good if e['nx'] else bad,
             'stack non-executable' if e['nx'] else 'executable stack'),
            ('RELRO', {'full': good, 'partial': warn, 'none': bad}[e['relro']],
             {'full': 'full, GOT read-only',
              'partial': 'partial, GOT still writable',
              'none': 'none'}[e['relro']]),
            ('Stack Canary', good if canary else bad,
             ('%d guarded function%s' % (canary, '' if canary == 1 else 's'))
             if canary else 'no stack protector'),
            ('CET / IBT', cet,
             'endbr64 on %.0f%% of functions' % (endbr_pct)),
            ('FORTIFY', good if e['fortify'] else warn,
             '_chk wrappers present' if e['fortify'] else 'not used'),
        ]
        if e['runpath']:
            rows.append(('RUNPATH', bad, 'set: %s' % (e['runpath'])))

        fig, ax = self.graph_axes(figsize=(7.6, 0.62 * len(rows) + 0.5))
        ax.set_axis_off()
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(0.0, len(rows))
        for i, (name, color, detail) in enumerate(rows):
            y = len(rows) - 1 - i + 0.5
            ax.add_patch(matplotlib.patches.FancyBboxPatch(
                (0.02, y - 0.34), 0.055, 0.68,
                boxstyle='round,pad=0.005,rounding_size=0.02',
                linewidth=0, facecolor=color, mutation_aspect=0.4,
                zorder=2))
            ax.text(0.10, y, name, va='center', ha='left', fontsize=11,
                    color=style['ink'], fontweight='bold')
            ax.text(0.42, y, detail, va='center', ha='left', fontsize=10,
                    color=style['ink'])
        self.graph_render(fig, self.opts.graph_card_filename,
                GRAPH_DESCRIPTIONS['hardening-card'])


    def graph_mitigation_coverage(self):
        if not self.db:
            self.graph_skip(self.opts.graph_coverage_filename)
            return
        style = self.graph_style()
        endbr, canary, thunks = self.coverage()
        n = len(self.db)
        fig, ax = self.graph_axes(figsize=(8.0, 2.4))
        ax.set_axis_off()
        self.graph_proportion_row(ax, 1.0, (endbr, n - endbr),
                ('With endbr64', 'Without'),
                (style['good'], style['bad']),
                'CET / Indirect Branch Tracking')
        self.graph_proportion_row(ax, 0.0, (canary, n - canary),
                ('With Canary', 'Without'),
                (style['good'], style['bad']),
                'Stack Protector')
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(-0.4, 1.6)
        self.graph_render(fig, self.opts.graph_coverage_filename,
                GRAPH_DESCRIPTIONS['hardening-coverage'])


    def graph_largest_unprotected(self):
        entries = sorted((f for f in self.db.values() if not f['canary']),
                key=lambda f: f['size'], reverse=True)[:20]
        if not entries:
            self.graph_skip(self.opts.graph_unprotected_filename)
            return
        names = [f['name'] for f in entries]
        sizes = [f['size'] for f in entries]
        fig, ax = self.graph_axes(xlabel='Function Size [Byte]')
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, sizes, height=0.72, color=self.graph_value_colors(sizes))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True)
        self.graph_render(fig, self.opts.graph_unprotected_filename,
                GRAPH_DESCRIPTIONS['hardening-unprotected'])


    def show(self):
        endbr, canary, thunks = self.coverage()
        n = len(self.db)
        if not hasattr(self, 'elf'):
            self.elf = self.elf_mitigations()
        e = self.elf

        self.msg_underline("Hardening Analysis", pre_news=2, post_news=2)
        self.msg("Number of analyzed functions: %d\n\n" % (n))

        self.msg("Load-time mitigations (ELF headers):\n")
        self.msg("    PIE (position independent):    %s\n" %
                ("yes" if e['pie'] else "no - fixed load address"))
        self.msg("    NX (non-executable stack):     %s\n" %
                ("yes" if e['nx'] else "no - stack is executable"))
        self.msg("    RELRO:                         %s\n" % (e['relro']))
        self.msg("    FORTIFY (_chk wrappers):       %s\n" %
                ("yes" if e['fortify'] else "no"))
        if e['runpath']:
            self.msg("    RUNPATH set:                   %s\n" % (e['runpath']))
        self.msg("\n")

        if self.percent(n, endbr) >= 90.0:
            verdict = "enabled"
        elif endbr > 0:
            verdict = "partial"
        else:
            verdict = "absent"
        self.msg("CET / IBT (-fcf-protection): %s\n" % (verdict))
        self.msg("    functions starting with endbr64: %d of %d  [ %5.2f%% ]\n" %
                (endbr, n, self.percent(n, endbr)))
        self.msg("    note: static functions only called directly need no endbr64\n")
        self.msg("Stack protector (-fstack-protector):\n")
        self.msg("    functions loading the canary (%%fs:0x28): %d of %d  [ %5.2f%% ]\n" %
                (canary, n, self.percent(n, canary)))
        self.msg("    note: only functions with stack buffers get a canary,\n")
        self.msg("    and only analyzed function bodies are scanned - without\n")
        self.msg("    a .symtab the static functions are invisible\n")
        self.msg("Retpoline thunks (__x86_indirect_thunk_*): %d\n" % (thunks))
        self.msg("Speculation barriers (lfence): %d\n" % (self.lfences))

        missing = [f for f in self.db.values()
                   if f['first'] not in ('endbr64', 'endbr32')]
        if endbr and missing:
            self.msg_underline("Functions Without endbr64", pre_news=2,
                    post_news=2)
            fmt = "%%%d.%ds: %%7d byte\n" % \
                    (self.strlen_longest_funcname, self.strlen_longest_funcname)
            for f in sorted(missing, key=lambda f: f['size'], reverse=True)[:10]:
                self.msg(fmt % (f['name'], f['size']))

        self.write_json('hardening', self.json_data())

        if self.opts.graph_card:
            self.graph_hardening_card()
        if self.opts.graph_coverage:
            self.graph_mitigation_coverage()
        if self.opts.graph_unprotected:
            self.graph_largest_unprotected()



class RegisterAnalyzer(Common):

    GRAPHS = [
        ('usage', 'register-usage.png', 'general purpose register usage'),
        ('classes', 'register-classes.png', 'register class shares'),
        ('addressing', 'register-addressing.png', 'operand and addressing forms'),
    ]

    GP_ORDER = ['rax', 'rbx', 'rcx', 'rdx', 'rsi', 'rdi', 'rbp', 'rsp',
                'r8', 'r9', 'r10', 'r11', 'r12', 'r13', 'r14', 'r15']
    CALLER_SAVED = ('rax', 'rcx', 'rdx', 'rsi', 'rdi',
                    'r8', 'r9', 'r10', 'r11')
    CALLEE_SAVED = ('rbx', 'rbp', 'r12', 'r13', 'r14', 'r15')
    FORMS = ['Register', 'Immediate', 'Memory', 'Memory (RIP-Relative)',
             'Memory (SIB)']

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()
        self.regs = dict()
        self.simd = 0
        self.forms = dict((form, 0) for form in RegisterAnalyzer.FORMS)
        self.family = self.build_family_table()


    def build_family_table(self):
        table = dict()
        pairs = [('rax', 'eax ax al ah'), ('rbx', 'ebx bx bl bh'),
                 ('rcx', 'ecx cx cl ch'), ('rdx', 'edx dx dl dh'),
                 ('rsi', 'esi si sil'), ('rdi', 'edi di dil'),
                 ('rbp', 'ebp bp bpl'), ('rsp', 'esp sp spl')]
        for family, subs in pairs:
            table[family] = family
            for sub in subs.split():
                table[sub] = family
        for i in range(8, 16):
            family = 'r%d' % (i)
            table[family] = family
            for suffix in ('d', 'w', 'b'):
                table['r%d%s' % (i, suffix)] = family
        return table


    def parse_local_options(self):
        parser = module_parser("register",
                "Register and addressing usage across all instructions.")
        add_graph_arguments(parser, RegisterAnalyzer.GRAPHS)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, RegisterAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary
        self.verbose("Analyze binary: %s\n" % (self.opts.filename))


    def run(self):
        self.parser = Parser(self.opts)
        self.parser.run(self)
        self.show()


    def account_operand(self, operand):
        if operand.startswith('$'):
            self.forms['Immediate'] += 1
        elif '(' in operand:
            if '(%rip)' in operand:
                self.forms['Memory (RIP-Relative)'] += 1
            elif ',' in operand[operand.index('('):]:
                self.forms['Memory (SIB)'] += 1
            else:
                self.forms['Memory'] += 1
        elif operand.startswith('%') or operand.startswith('*%'):
            self.forms['Register'] += 1
        else:
            self.forms['Memory'] += 1

        for name in re.findall(r'%([a-z][a-z0-9]*)', operand):
            family = self.family.get(name)
            if family:
                self.regs[family] = self.regs.get(family, 0) + 1
            elif name.startswith(('xmm', 'ymm', 'zmm', 'mm')):
                self.simd += 1


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        for operand in (atom.src, atom.dst):
            if operand is not None:
                self.account_operand(operand)


    def percent(self, whole, part):
        if whole == 0:
            return 0.0
        return (float(part) / float(whole)) * 100.0


    def json_data(self):
        caller = sum(self.regs.get(r, 0) for r in RegisterAnalyzer.CALLER_SAVED)
        callee = sum(self.regs.get(r, 0) for r in RegisterAnalyzer.CALLEE_SAVED)
        rex = sum(cnt for reg, cnt in self.regs.items() if reg.startswith('r')
                  and reg[1:].isdigit())
        return {
            'registers': self.regs,
            'simd-mentions': self.simd,
            'caller-saved': caller,
            'callee-saved': callee,
            'rex-mentions': rex,
            'operand-forms': self.forms,
        }


    def graph_register_usage(self):
        counts = [self.regs.get(reg, 0) for reg in RegisterAnalyzer.GP_ORDER]
        if sum(counts) == 0:
            self.graph_skip(self.opts.graph_usage_filename)
            return
        fig, ax = self.graph_axes(xlabel='Register Mentions')
        self.graph_grid(ax, 'x')
        y = range(len(RegisterAnalyzer.GP_ORDER))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(RegisterAnalyzer.GP_ORDER, family='monospace')
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True, total=sum(counts))
        self.graph_render(fig, self.opts.graph_usage_filename,
                GRAPH_DESCRIPTIONS['register-usage'])


    def graph_register_classes(self):
        gp = sum(self.regs.values())
        if gp == 0:
            self.graph_skip(self.opts.graph_classes_filename)
            return
        style = self.graph_style()
        caller = sum(self.regs.get(r, 0) for r in RegisterAnalyzer.CALLER_SAVED)
        callee = sum(self.regs.get(r, 0) for r in RegisterAnalyzer.CALLEE_SAVED)
        rsp = self.regs.get('rsp', 0)
        rex = sum(cnt for reg, cnt in self.regs.items() if reg.startswith('r')
                  and reg[1:].isdigit())
        fig, ax = self.graph_axes(figsize=(8.0, 3.0))
        ax.set_axis_off()
        self.graph_proportion_row(ax, 2.0, (caller, callee, rsp),
                ('Caller-Saved', 'Callee-Saved', 'Stack Pointer'),
                (style['primary'], style['secondary'], style['good']),
                'Save Class')
        self.graph_proportion_row(ax, 1.0, (gp - rex, rex),
                ('Legacy (rax-rdi)', 'REX (r8-r15)'),
                (style['primary'], style['secondary']),
                'REX Prefix Need')
        self.graph_proportion_row(ax, 0.0, (gp, self.simd),
                ('General Purpose', 'SIMD'),
                (style['primary'], style['secondary']),
                'Register Kind')
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(-0.4, 2.6)
        self.graph_render(fig, self.opts.graph_classes_filename,
                GRAPH_DESCRIPTIONS['register-classes'])


    def graph_addressing_forms(self):
        total = sum(self.forms.values())
        if total == 0:
            self.graph_skip(self.opts.graph_addressing_filename)
            return
        entries = sorted(self.forms.items(), key=lambda item: item[1],
                reverse=True)
        names = [name for name, cnt in entries]
        counts = [cnt for name, cnt in entries]
        fig, ax = self.graph_axes(xlabel='Operands', figsize=(8.0, 3.2))
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, counts, height=0.72, color=self.graph_value_colors(counts))
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.margins(x=0.10)
        self.graph_bar_labels(ax, bars, horizontal=True, total=total)
        self.graph_render(fig, self.opts.graph_addressing_filename,
                GRAPH_DESCRIPTIONS['register-addressing'])


    def show(self):
        gp = sum(self.regs.values())
        self.msg_underline("Register and Addressing Analysis", pre_news=2,
                post_news=2)
        self.msg("General purpose register mentions: %d\n" % (gp))
        self.msg("SIMD register mentions: %d\n" % (self.simd))

        self.msg_underline("General Purpose Registers", pre_news=2, post_news=2)
        for reg in RegisterAnalyzer.GP_ORDER:
            cnt = self.regs.get(reg, 0)
            self.msg("%-4s %10d  [ %5.2f%% ]\n" %
                    (reg, cnt, self.percent(gp, cnt)))

        caller = sum(self.regs.get(r, 0) for r in RegisterAnalyzer.CALLER_SAVED)
        callee = sum(self.regs.get(r, 0) for r in RegisterAnalyzer.CALLEE_SAVED)
        rex = sum(cnt for reg, cnt in self.regs.items() if reg.startswith('r')
                  and reg[1:].isdigit())
        self.msg_underline("Register Classes", pre_news=2, post_news=2)
        self.msg("Caller-saved: %10d  [ %5.2f%% ]\n" %
                (caller, self.percent(gp, caller)))
        self.msg("Callee-saved: %10d  [ %5.2f%% ]\n" %
                (callee, self.percent(gp, callee)))
        self.msg("REX (r8-r15): %10d  [ %5.2f%% ]\n" %
                (rex, self.percent(gp, rex)))

        total = sum(self.forms.values())
        self.msg_underline("Operand Forms", pre_news=2, post_news=2)
        for name, cnt in sorted(self.forms.items(), key=lambda item: item[1],
                reverse=True):
            self.msg("%-22s %10d  [ %5.2f%% ]\n" %
                    (name, cnt, self.percent(total, cnt)))

        self.write_json('register', self.json_data())

        if self.opts.graph_usage:
            self.graph_register_usage()
        if self.opts.graph_classes:
            self.graph_register_classes()
        if self.opts.graph_addressing:
            self.graph_addressing_forms()



class DiffCollector(Common):

    def __init__(self, opts, func_excluder):
        self.opts = opts
        self.func_excluder = func_excluder
        self.functions = dict()
        self.categories = dict()
        self.stack = dict()
        self.insn_cnt = 0


    def msg(self, msg):
        # swallow the parser banner, the diff module prints its own
        return 0


    def code_size(self):
        return sum(f['size'] for f in self.functions.values())


    def process(self, context, atom):
        if self.func_excluder and self.func_excluder.is_excluded(context.function_name):
            return
        name = context.function_name
        if name not in self.functions:
            self.functions[name] = { 'size': 0, 'insns': 0, 'starts': set() }
        func = self.functions[name]
        if context.function_start_address not in func['starts']:
            # duplicate function names are aggregated
            func['starts'].add(context.function_start_address)
            func['size'] += context.function_size
        func['insns'] += 1
        self.insn_cnt += 1

        cat = InstructionCategory.guess(atom.mnemonic)
        self.categories[cat] = self.categories.get(cat, 0) + 1

        ret = check_stack_mangling_op(atom)
        if ret and ret.stack_type == RetObj.STATIC:
            self.stack[name] = max(self.stack.get(name, 0), ret.val)



class DiffAnalyzer(Common):

    def __init__(self):
        self.func_excluder = FunctionExcluder()
        self.parse_local_options()


    GRAPHS = [
        ('changes', 'diff-changes.png', 'per function code size deltas'),
        ('categories', 'diff-categories.png', 'instruction category deltas'),
    ]

    def parse_local_options(self):
        parser = module_parser("diff",
                "Compare two builds: size, instruction mix and stack deltas.")
        add_graph_arguments(parser, DiffAnalyzer.GRAPHS)
        parser.add_argument('binary_old', help='ELF binary before the change')
        parser.add_argument('binary_new', help='ELF binary after the change')
        self.opts = parser.parse_args(sys.argv[2:])
        finish_graph_arguments(self.opts, DiffAnalyzer.GRAPHS)

        if self.opts.no_exclude:
            # empty list means there will never be a match
            self.func_excluder = None

        self.filename_old = self.opts.binary_old
        self.filename_new = self.opts.binary_new
        for filename in (self.filename_old, self.filename_new):
            if not os.path.isfile(filename):
                self.err("No such binary: %s\n" % (filename))
                sys.exit(1)


    def collect(self, filename):
        import copy
        opts = copy.copy(self.opts)
        opts.filename = filename
        collector = DiffCollector(opts, self.func_excluder)
        parser = Parser(opts)
        parser.run(collector)
        return collector


    def run(self):
        old = self.collect(self.filename_old)
        new = self.collect(self.filename_new)
        self.show(old, new)


    def delta_str(self, old, new):
        delta = new - old
        if old != 0 and delta != 0:
            return "%+d ( %+.1f%% )" % (delta, (float(delta) / old) * 100.0)
        return "%+d" % (delta)


    def show_summary(self, old, new):
        fmt = "%-18s %12s %12s   %s\n"
        self.msg(fmt % ("", "old", "new", "delta"))
        rows = [
            ("functions", len(old.functions), len(new.functions)),
            ("code size [byte]", old.code_size(), new.code_size()),
            ("instructions", old.insn_cnt, new.insn_cnt),
        ]
        for name, o, n in rows:
            self.msg(fmt % (name, o, n, self.delta_str(o, n)))


    def show_added_removed(self, title, functions, sign):
        if not functions:
            return
        self.msg_underline(title, pre_news=2, post_news=2)
        for name, size in sorted(functions.items(), key=lambda item: item[1],
                                 reverse=True):
            self.msg("%s: %s%d byte\n" % (name, sign, size))


    def show_size_changes(self, old, new):
        changes = []
        for name in old.functions.keys() & new.functions.keys():
            size_old = old.functions[name]['size']
            size_new = new.functions[name]['size']
            if size_old != size_new:
                changes.append((name, size_old, size_new))
        if not changes:
            return
        self.msg_underline("Function Size Changes", pre_news=2, post_news=2)
        changes.sort(key=lambda c: abs(c[2] - c[1]), reverse=True)
        for name, size_old, size_new in changes:
            self.msg("%s: %d -> %d byte (%+d)\n" %
                    (name, size_old, size_new, size_new - size_old))


    def show_category_changes(self, old, new):
        changes = []
        for cat in old.categories.keys() | new.categories.keys():
            cnt_old = old.categories.get(cat, 0)
            cnt_new = new.categories.get(cat, 0)
            if cnt_old != cnt_new:
                changes.append((cat, cnt_old, cnt_new))
        if not changes:
            return
        self.msg_underline("Instruction Category Changes", pre_news=2, post_news=2)
        changes.sort(key=lambda c: abs(c[2] - c[1]), reverse=True)
        for cat, cnt_old, cnt_new in changes:
            self.msg("%s: %d -> %d (%+d)\n" % (InstructionCategory.str(cat),
                     cnt_old, cnt_new, cnt_new - cnt_old))


    def show_stack_changes(self, old, new):
        changes = []
        for name in old.stack.keys() | new.stack.keys():
            val_old = old.stack.get(name, 0)
            val_new = new.stack.get(name, 0)
            if val_old != val_new:
                changes.append((name, val_old, val_new))
        if not changes:
            return
        self.msg_underline("Stack Usage Changes", pre_news=2, post_news=2)
        changes.sort(key=lambda c: abs(c[2] - c[1]), reverse=True)
        for name, val_old, val_new in changes:
            self.msg("%s: %d -> %d byte (%+d)\n" %
                    (name, val_old, val_new, val_new - val_old))


    def json_data(self, old, new, added, removed):
        size_changes = []
        for name in old.functions.keys() & new.functions.keys():
            size_old = old.functions[name]['size']
            size_new = new.functions[name]['size']
            if size_old != size_new:
                size_changes.append({ 'name': name, 'old': size_old,
                                      'new': size_new })
        size_changes.sort(key=lambda c: abs(c['new'] - c['old']), reverse=True)
        categories = dict()
        for cat in old.categories.keys() | new.categories.keys():
            categories[InstructionCategory.str(cat)] = {
                'old': old.categories.get(cat, 0),
                'new': new.categories.get(cat, 0),
            }
        stack_changes = []
        for name in old.stack.keys() | new.stack.keys():
            val_old = old.stack.get(name, 0)
            val_new = new.stack.get(name, 0)
            if val_old != val_new:
                stack_changes.append({ 'name': name, 'old': val_old,
                                       'new': val_new })
        stack_changes.sort(key=lambda c: abs(c['new'] - c['old']), reverse=True)
        return {
            'binary-old': os.path.abspath(self.filename_old),
            'binary-new': os.path.abspath(self.filename_new),
            'functions': { 'old': len(old.functions),
                           'new': len(new.functions) },
            'code-size': { 'old': old.code_size(), 'new': new.code_size() },
            'instructions': { 'old': old.insn_cnt, 'new': new.insn_cnt },
            'added-functions': added,
            'removed-functions': removed,
            'size-changes': size_changes,
            'category-changes': categories,
            'stack-changes': stack_changes,
        }


    def graph_diverging(self, entries, filename, xlabel, description):
        # entries: (label, delta), growth to the right in warm color,
        # shrinkage to the left in a calm one
        style = self.graph_style()
        entries = sorted(entries, key=lambda e: abs(e[1]), reverse=True)[:20]
        entries.sort(key=lambda e: e[1], reverse=True)
        names = [name for name, delta in entries]
        deltas = [delta for name, delta in entries]
        colors = [style['bad'] if d > 0 else style['good'] for d in deltas]
        height = max(2.2, 0.8 + 0.28 * len(names))
        fig, ax = self.graph_axes(xlabel=xlabel, figsize=(8.0, height))
        self.graph_grid(ax, 'x')
        y = range(len(names))
        bars = ax.barh(y, deltas, height=0.72, color=colors)
        ax.set_yticks(list(y))
        ax.set_yticklabels(names)
        ax.invert_yaxis()
        ax.axvline(0, color=style['frame'], linewidth=0.8, zorder=3)
        ax.margins(x=0.12)
        self.graph_bar_labels(ax, bars, horizontal=True, fmt='%+d')
        self.graph_render(fig, filename, description)


    def graph_changes(self, old, new, added, removed):
        entries = [(name, size) for name, size in added.items()]
        entries += [(name, -size) for name, size in removed.items()]
        for name in old.functions.keys() & new.functions.keys():
            delta = new.functions[name]['size'] - old.functions[name]['size']
            if delta != 0:
                entries.append((name, delta))
        if not entries:
            self.graph_skip(self.opts.graph_changes_filename)
            return
        self.graph_diverging(entries, self.opts.graph_changes_filename,
                'Code Size Delta [Byte]', GRAPH_DESCRIPTIONS['diff-changes'])


    def graph_categories(self, old, new):
        entries = []
        for cat in old.categories.keys() | new.categories.keys():
            delta = new.categories.get(cat, 0) - old.categories.get(cat, 0)
            if delta != 0:
                entries.append((InstructionCategory.str(cat), delta))
        if not entries:
            self.graph_skip(self.opts.graph_categories_filename)
            return
        self.graph_diverging(entries, self.opts.graph_categories_filename,
                'Instruction Count Delta', GRAPH_DESCRIPTIONS['diff-categories'])


    def show(self, old, new):
        self.msg_underline("Binary Diff", pre_news=1, post_news=2)
        self.msg("%s -> %s\n\n" % (self.filename_old, self.filename_new))
        self.show_summary(old, new)

        added = dict((name, f['size']) for name, f in new.functions.items()
                     if name not in old.functions)
        removed = dict((name, f['size']) for name, f in old.functions.items()
                       if name not in new.functions)
        self.show_added_removed("Added Functions", added, '+')
        self.show_added_removed("Removed Functions", removed, '-')
        self.show_size_changes(old, new)
        self.show_category_changes(old, new)
        self.show_stack_changes(old, new)

        self.write_json('diff', self.json_data(old, new, added, removed),
                binary=self.filename_new)

        if self.opts.graph_changes:
            self.graph_changes(old, new, added, removed)
        if self.opts.graph_categories:
            self.graph_categories(old, new)



class InfoAnalyzer(Common):

    # ELF metadata gathered from external standard tools. Unlike the
    # other modules this one does not disassemble, it wraps eu-readelf
    # and file(1) and fails hard when they are missing.

    def __init__(self):
        self.parse_local_options()


    def parse_local_options(self):
        parser = module_parser("info",
                "ELF metadata and security features via eu-readelf and file.",
                no_exclude=False)
        parser.add_argument('binary', help='ELF binary to analyze')
        self.opts = parser.parse_args(sys.argv[2:])
        if not os.path.isfile(self.opts.binary):
            self.err("No such binary: %s\n" % (self.opts.binary))
            sys.exit(1)
        self.opts.filename = self.opts.binary


    def require_tool(self, names):
        for name in names:
            path = shutil.which(name)
            if path:
                return path
        self.err("required tool not found: %s\n" % (' or '.join(names)))
        sys.exit(1)


    def run_tool(self, argv):
        try:
            result = subprocess.run(argv, stdout=subprocess.PIPE,
                    stderr=subprocess.PIPE, env=dict(os.environ, LC_ALL='C'))
        except OSError as e:
            self.err("failed to run %s: %s\n" % (argv[0], e))
            sys.exit(1)
        if result.returncode != 0:
            self.err("%s failed on %s:\n%s" % (argv[0], self.opts.filename,
                     result.stderr.decode('utf-8', 'replace')))
            sys.exit(1)
        return result.stdout.decode('utf-8', 'replace')


    def parse_metadata(self, readelf, file_desc):
        data = dict()
        data['file'] = file_desc

        match = re.search(r'Class:\s+(\S+)', readelf)
        data['class'] = match.group(1) if match else None
        match = re.search(r'Type:\s+(.+)', readelf)
        type_str = match.group(1).strip() if match else ''
        is_dyn = type_str.startswith('DYN')
        match = re.search(r'Machine:\s+(.+)', readelf)
        data['machine'] = match.group(1).strip() if match else None

        match = re.search(r'program interpreter:\s+([^\]]+)\]', readelf)
        data['interpreter'] = match.group(1).strip() if match else None
        data['pie'] = is_dyn and data['interpreter'] is not None
        data['shared-object'] = is_dyn and data['interpreter'] is None

        data['needed'] = re.findall(r'NEEDED.*?\[(.+?)\]', readelf)
        match = re.search(r'SONAME.*?\[(.+?)\]', readelf)
        data['soname'] = match.group(1) if match else None
        match = re.search(r'(?:RUNPATH|RPATH).*?\[(.+?)\]', readelf)
        data['runpath'] = match.group(1) if match else None

        bind_now = bool(re.search(r'\bBIND_NOW\b', readelf)) or \
                bool(re.search(r'FLAGS_1.*\bNOW\b', readelf))
        data['bind-now'] = bind_now
        has_relro = 'GNU_RELRO' in readelf
        data['relro'] = 'full' if has_relro and bind_now else \
                ('partial' if has_relro else 'none')

        stack = re.search(r'GNU_STACK.*', readelf)
        if stack:
            data['nx'] = 'RWE' not in stack.group(0)
        else:
            # a missing GNU_STACK means the loader defaults to an
            # executable stack
            data['nx'] = False

        data['stripped'] = not bool(re.search(r'\.symtab\b', readelf))
        match = re.search(r'Build ID:\s+([0-9a-f]+)', readelf)
        data['build-id'] = match.group(1) if match else None
        match = re.search(r'There are (\d+) section headers', readelf) or \
                re.search(r'Number of section headers[^:]*:\s+(\d+)', readelf)
        data['sections'] = int(match.group(1)) if match else None
        # Go leaves unmistakable traces even in a stripped binary
        data['go'] = '.gopclntab' in readelf or '.note.go.buildid' in readelf
        return data


    def gather(self):
        readelf = self.require_tool(['eu-readelf', 'readelf'])
        file_tool = self.require_tool(['file'])
        self.verbose("using %s and %s\n" % (readelf, file_tool))
        readelf_text = self.run_tool([readelf, '-h', '-l', '-d', '-S', '-n',
                self.opts.filename])
        file_out = self.run_tool([file_tool, '-L', '-b', self.opts.filename])
        return self.parse_metadata(readelf_text, file_out.strip())


    def yesno(self, value):
        return 'yes' if value else 'no'


    def run(self):
        data = self.gather()
        self.msg_underline("ELF Info", pre_news=0, post_news=2)
        self.msg("%s\n\n" % (self.opts.filename))
        self.msg("file:         %s\n" % (data['file']))
        self.msg("class:        %s\n" % (data['class']))
        kind = 'shared object' if data['shared-object'] else \
                ('PIE executable' if data['pie'] else 'executable')
        self.msg("kind:         %s\n" % (kind))
        self.msg("machine:      %s\n" % (data['machine']))
        if data['interpreter']:
            self.msg("interpreter:  %s\n" % (data['interpreter']))
        if data['build-id']:
            self.msg("build-id:     %s\n" % (data['build-id']))
        self.msg("stripped:     %s\n" % (self.yesno(data['stripped'])))
        if data.get('go'):
            self.msg("go binary:    yes\n")
        if data['sections'] is not None:
            self.msg("sections:     %d\n" % (data['sections']))
        if data['soname']:
            self.msg("soname:       %s\n" % (data['soname']))

        self.msg_underline("Security Features", pre_news=2, post_news=2)
        self.msg("PIE:          %s\n" % (self.yesno(data['pie'])))
        self.msg("RELRO:        %s\n" % (data['relro']))
        self.msg("BIND_NOW:     %s\n" % (self.yesno(data['bind-now'])))
        self.msg("NX stack:     %s\n" % (self.yesno(data['nx'])))
        self.msg("RUNPATH:      %s\n" % (data['runpath'] or '(none)'))

        self.msg_underline("Shared Library Dependencies (%d)" %
                (len(data['needed'])), pre_news=2, post_news=2)
        for lib in data['needed']:
            self.msg("%s\n" % (lib))
        if not data['needed']:
            self.msg("(statically linked or none)\n")

        self.write_json('info', data)



class MachineCodeAnalyzer:

    modes = {
       "function":    [ "FunctionAnalyzer",    "Function anatomy information" ],
       "instruction": [ "InstructionAnalyzer", "Information about instructions" ],
       "branch":      [ "BranchAnalyzer",      "Information about branches and jumps" ],
       "stack":       [ "StackAnalyzer",       "Stack usage analyzer" ],
       "atomic":      [ "AtomicAnalyzer",      "Atomic operation and lock analyzer" ],
       "layout":      [ "LayoutAnalyzer",      "Hot/cold code layout analyzer" ],
       "idiom":       [ "IdiomAnalyzer",       "Instruction sequence idioms" ],
       "call":        [ "CallAnalyzer",        "Call structure analyzer" ],
       "hardening":   [ "HardeningAnalyzer",   "Mitigation coverage analyzer" ],
       "register":    [ "RegisterAnalyzer",    "Register and addressing usage" ],
       "info":        [ "InfoAnalyzer",        "ELF metadata and security features" ],
       "diff":        [ "DiffAnalyzer",        "Compare two binaries" ]
            }


    def __init__(self):
        InstructionCategory.init_instruction_table()


    def print_version(self):
        sys.stdout.write("%s\n" % (__version__))


    def print_usage(self):
        prog = os.path.basename(sys.argv[0])
        sys.stderr.write("Usage: %s [-h | --help] [--version]"
                         " <module> [<module-options>] <binary>...\n"
                         "Module options: %s <module> --help\n" % (prog, prog))


    def print_modules(self):
        for i in MachineCodeAnalyzer.modes.keys():
            sys.stderr.write("   %-15s - %s\n" % (i, MachineCodeAnalyzer.modes[i][1]))


    def args_contains(self, argv, *cmds):
        for cmd in cmds:
            for arg in argv:
                if arg == cmd: return True
        return False


    def parse_global_otions(self):
        if len(sys.argv) < 2:
            self.print_usage()
            sys.stderr.write("Available modules:\n")
            self.print_modules()
            return None

        # --version can be placed somewhere in the
        # command line and will evalutated always: it is
        # a global option
        if self.args_contains(sys.argv, "--version"):
            self.print_version()
            return None

        # -h | --help as first argument is treated special
        # and has other meaning as a submodule
        if self.args_contains(sys.argv[1:2], "-h", "--help"):
            self.print_usage()
            sys.stderr.write("Available modules:\n")
            self.print_modules()
            return None

        submodule = sys.argv[1].lower()
        if submodule not in MachineCodeAnalyzer.modes:
            self.print_usage()
            sys.stderr.write("Module \"%s\" not known, available modules are:\n" %
                             (submodule))
            self.print_modules()
            return None

        classname = MachineCodeAnalyzer.modes[submodule][0]
        return classname


    def run(self):
        classtring = self.parse_global_otions()
        if not classtring:
            return 1

        classinstance = globals()[classtring]()
        classinstance.run()
        return 0


if __name__ == "__main__":
    try:
        mca = MachineCodeAnalyzer()
        sys.exit(mca.run())
    except KeyboardInterrupt:
        sys.stderr.write("SIGINT received, exiting\n")
        sys.exit(1)