diff --git a/elftools/dwarf/callframe.py b/elftools/dwarf/callframe.py
index 3f6b735..f656ee2 100644
--- a/elftools/dwarf/callframe.py
+++ b/elftools/dwarf/callframe.py
@@ -6,62 +6,13 @@
 # Eli Bendersky (eliben@gmail.com)
 # This code is in the public domain
 #-------------------------------------------------------------------------------
+import copy
+from collections import namedtuple
 from ..common.utils import (struct_parse, dwarf_assert, preserve_stream_pos)
 from .structs import DWARFStructs
 from .constants import * 
 
 
-class CallFrameInstruction(object):
-    """ A decoded instruction in the CFI section. opcode is the instruction
-        opcode, numeric - as it appears in the section. args is a list of
-        arguments (including arguments embedded in the low bits of some
-        instructions, when applicable).
-    """
-    def __init__(self, opcode, args):
-        self.opcode = opcode
-        self.args = args
-
-    def __repr__(self):
-        return '%s (0x%x): %s' % (
-            instruction_name(self.opcode), self.opcode, self.args)
-
-
-class CIE(object):
-    """ CIE - Common Information Entry.
-        Contains a header and a list of instructions (CallFrameInstruction).
-        offset: the offset of this entry from the beginning of the section
-    """
-    def __init__(self, header, structs, instructions, offset):
-        self.header = header
-        self.structs = structs
-        self.instructions = instructions
-        self.offset = offset
-
-    def __getitem__(self, name):
-        """ Implement dict-like access to header entries
-        """
-        return self.header[name]
-
-
-class FDE(object):
-    """ FDE - Frame Description Entry.
-        Contains a header, a list of instructions (CallFrameInstruction) and a
-        reference to the CIE object associated with this FDE.
-        offset: the offset of this entry from the beginning of the section
-    """
-    def __init__(self, header, structs, instructions, offset, cie):
-        self.header = header
-        self.structs = structs
-        self.instructions = instructions
-        self.offset = offset
-        self.cie = cie
-
-    def __getitem__(self, name):
-        """ Implement dict-like access to header entries
-        """
-        return self.header[name]
-
-
 class CallFrameInfo(object):
     """ DWARF CFI (Call Frame Info)
         
@@ -239,6 +190,190 @@
         return _OPCODE_NAME_MAP[primary]
 
 
+class CallFrameInstruction(object):
+    """ An instruction in the CFI section. opcode is the instruction
+        opcode, numeric - as it appears in the section. args is a list of
+        arguments (including arguments embedded in the low bits of some
+        instructions, when applicable), decoded from the stream.
+    """
+    def __init__(self, opcode, args):
+        self.opcode = opcode
+        self.args = args
+
+    def __repr__(self):
+        return '%s (0x%x): %s' % (
+            instruction_name(self.opcode), self.opcode, self.args)
+
+
+class CFIEntry(object):
+    """ A common base class for CFI entries.
+        Contains a header and a list of instructions (CallFrameInstruction).
+        offset: the offset of this entry from the beginning of the section
+        cie: for FDEs, a CIE pointer is required
+    """
+    def __init__(self, header, structs, instructions, offset, cie=None):
+        self.header = header
+        self.structs = structs
+        self.instructions = instructions
+        self.offset = offset
+        self.cie = cie
+        self._decoded_table = None
+
+    def get_decoded(self):
+        if self._decoded_table is None:
+            self._decoded_table = self._decode_CFI_table()
+        return self._decoded_table
+
+    def __getitem__(self, name):
+        """ Implement dict-like access to header entries
+        """
+        return self.header[name]
+
+    def _decode_CFI_table(self):
+        """ Decode the instructions contained in the given CFI entry and return
+            a DecodedCallFrameTable.
+        """
+        if isinstance(self, CIE):
+            cie = self
+            cur_line = dict(pc=0, cfa=None)
+            reg_order = []
+        else: # FDE
+            cie = self.cie
+            cie_decoded_table = cie.get_decoded()
+            cur_line = cie_decoded_table.table[-1]
+            cur_line['pc'] = self['initial_location']
+            reg_order = cie_decoded_table.reg_order
+        
+        table = []
+        line_stack = []
+
+        def _add_to_order(regnum):
+            if regnum not in cur_line:
+                reg_order.append(regnum)
+
+        for instr in self.instructions:
+            name = instruction_name(instr.opcode)
+
+            if name == 'DW_CFA_set_loc':
+                table.append(copy.copy(cur_line))
+                cur_line['pc'] = instr.args[0]
+            elif name in (  'DW_CFA_advance_loc1', 'DW_CFA_advance_loc2',
+                            'DW_CFA_advance_loc4', 'DW_CFA_advance_loc'):
+                table.append(copy.copy(cur_line))
+                cur_line['pc'] += instr.args[0] * cie['code_alignment_factor']
+            elif name == 'DW_CFA_def_cfa':
+                cur_line['cfa'] = CFARule(
+                    reg=instr.args[0],
+                    offset=instr.args[1])
+            elif name == 'DW_CFA_def_cfa_sf':
+                cur_line['cfa'] = CFARule(
+                    reg=instr.args[0],
+                    offset=instr.args[1] * cie['code_alignment_factor'])
+            elif name == 'DW_CFA_def_cfa_register':
+                cur_line['cfa'] = CFARule(
+                    reg=instr.args[0],
+                    offset=cur_line['cfa'].offset)
+            elif name == 'DW_CFA_def_cfa_offset':
+                cur_line['cfa'] = CFARule(
+                    reg=cur_line['cfa'].reg,
+                    offset=instr.args[0])
+            elif name == 'DW_CFA_def_cfa_expression':
+                cur_line['cfa'] = CFARule(expr=instr.args[0])
+            elif name == 'DW_CFA_undefined':
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(RegisterRule.UNDEFINED)
+            elif name == 'DW_CFA_same_value':
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(RegisterRule.SAME_VALUE)
+            elif name in (  'DW_CFA_offset', 'DW_CFA_offset_extended',
+                            'DW_CFA_offset_extended_sf'):
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(
+                    RegisterRule.OFFSET,
+                    instr.args[1] * cie['data_alignment_factor'])
+            elif name in ('DW_CFA_val_offset', 'DW_CFA_val_offset_sf'):
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(
+                    RegisterRule.VAL_OFFSET,
+                    instr.args[1] * cie['data_alignment_factor'])
+            elif name == 'DW_CFA_register':
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(
+                    RegisterRule.REGISTER,
+                    instr.args[1])
+            elif name == 'DW_CFA_expression':
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(
+                    RegisterRule.EXPRESSION,
+                    instr.args[1])
+            elif name == 'DW_CFA_val_expression':
+                _add_to_order(instr.args[0])
+                cur_line[instr.args[0]] = RegisterRule(
+                    RegisterRule.VAL_EXPRESSION,
+                    instr.args[1])
+            elif name in ('DW_CFA_restore', 'DW_CFA_restore_extended'):
+                _add_to_order(instr.args[0])
+                dwarf_assert(
+                    isinstance(self, FDE),
+                    '%s instruction must be in a FDE' % name)
+                last_line_in_CIE = self.cie.get_decoded().table[-1]
+                dwarf_assert(
+                    instr.args[0] in last_line_in_CIE,
+                    '%s: can not find register in CIE')
+                cur_line[instr.args[0]] = last_line_in_CIE
+            elif name == 'DW_CFA_remember_state':
+                line_stack.append(cur_line)
+            elif name == 'DW_CFA_restore_state':
+                cur_line = line_stack.pop()
+
+        if len(self.instructions) > 0:
+            table.append(cur_line)
+        return DecodedCallFrameTable(table=table, reg_order=reg_order)
+
+
+class CIE(CFIEntry):
+    pass
+
+
+class FDE(CFIEntry):
+    pass
+
+
+class RegisterRule(object):
+    """ An enumeration of register rules (DWARFv3 section 6.4.1)
+    """
+    UNDEFINED = 'UNDEFINED'
+    SAME_VALUE = 'SAME_VALUE'
+    OFFSET = 'OFFSET'
+    VAL_OFFSET = 'VAL_OFFSET'
+    REGISTER = 'REGISTER'
+    EXPRESSION = 'EXPRESSION'
+    VAL_EXPRESSION = 'VAL_EXPRESSION'
+    ARCHITECTURAL = 'ARCHITECTURAL'
+
+    def __init__(self, type, arg=None):
+        self.type = type
+        self.arg = arg
+
+    def __repr__(self):
+        return 'RegisterRule(%s, %s)' % (self.type, self.arg)
+
+
+class CFARule(object):
+    def __init__(self, reg=None, offset=None, expr=None):
+        self.reg = reg
+        self.offset = offset
+        self.expr = expr
+
+    def __repr__(self):
+        return 'CFARule(reg=%s, offset=%s, expr=%s)' % (
+            self.reg, self.offset, self.expr)
+
+
+DecodedCallFrameTable = namedtuple(
+    'DecodedCallFrameTable', 'table reg_order')
+
+
 #---------------- PRIVATE ----------------#
 
 _PRIMARY_MASK = 0b11000000
diff --git a/elftools/dwarf/descriptions.py b/elftools/dwarf/descriptions.py
index 0a45065..1cf2633 100644
--- a/elftools/dwarf/descriptions.py
+++ b/elftools/dwarf/descriptions.py
@@ -87,9 +87,13 @@
         elif name in (  'DW_CFA_remember_state', 'DW_CFA_restore_state',
                         'DW_CFA_nop'):
             s += '  %s\n' % name
-        elif name in ( 'DW_CFA_def_cfa', 'DW_CFA_def_cfa_sf'):
+        elif name == 'DW_CFA_def_cfa':
             s += '  %s: %s ofs %s\n' % (
                 name, _full_reg_name(instr.args[0]), instr.args[1])
+        elif name == 'DW_CFA_def_cfa_sf':
+            s += '  %s: %s ofs %s\n' % (
+                name, _full_reg_name(instr.args[0]),
+                instr.args[1] * cie['data_alignment_factor'])
         elif name == 'DW_CFA_def_cfa_offset':
             s += '  %s: %s\n' % (name, instr.args[0])
         elif name == 'DW_CFA_def_cfa_expression':
diff --git a/tests/test_callframe.py b/tests/test_callframe.py
index 5f7b00c..556f172 100644
--- a/tests/test_callframe.py
+++ b/tests/test_callframe.py
@@ -3,7 +3,8 @@
 
 sys.path.extend(['.', '..'])
 from elftools.dwarf.callframe import (
-    CallFrameInfo, CIE, FDE, instruction_name, CallFrameInstruction)
+    CallFrameInfo, CIE, FDE, instruction_name, CallFrameInstruction,
+    RegisterRule)
 from elftools.dwarf.structs import DWARFStructs
 from elftools.dwarf.descriptions import (describe_CFI_instructions,
     set_global_machine_arch)
@@ -90,6 +91,33 @@
         self.assertInstruction(entries[1].instructions[20],
             'DW_CFA_nop', [])
 
+        # Now let's decode it...
+        decoded_CIE = entries[0].get_decoded()
+        self.assertEqual(decoded_CIE.reg_order, list(range(9)))
+        self.assertEqual(len(decoded_CIE.table), 1)
+        self.assertEqual(decoded_CIE.table[0]['cfa'].reg, 7)
+        self.assertEqual(decoded_CIE.table[0]['pc'], 0)
+        self.assertEqual(decoded_CIE.table[0]['cfa'].offset, 0)
+        self.assertEqual(decoded_CIE.table[0][4].type, RegisterRule.SAME_VALUE)
+        self.assertEqual(decoded_CIE.table[0][8].type, RegisterRule.REGISTER)
+        self.assertEqual(decoded_CIE.table[0][8].arg, 1)
+
+        decoded_FDE = entries[1].get_decoded()
+        self.assertEqual(decoded_FDE.reg_order, list(range(9)))
+        #self.assertEqual(len(decoded_FDE.table), 1)
+        self.assertEqual(decoded_FDE.table[0]['cfa'].reg, 7)
+        self.assertEqual(decoded_FDE.table[0]['cfa'].offset, 0)
+        self.assertEqual(decoded_FDE.table[0]['pc'], 0x11223344)
+        self.assertEqual(decoded_FDE.table[0][8].type, RegisterRule.REGISTER)
+        self.assertEqual(decoded_FDE.table[0][8].arg, 1)
+        self.assertEqual(decoded_FDE.table[1]['cfa'].reg, 7)
+        self.assertEqual(decoded_FDE.table[1]['cfa'].offset, 12)
+        self.assertEqual(decoded_FDE.table[2][8].type, RegisterRule.OFFSET)
+        self.assertEqual(decoded_FDE.table[2][8].arg, -4)
+        self.assertEqual(decoded_FDE.table[2][4].type, RegisterRule.SAME_VALUE)
+        self.assertEqual(decoded_FDE.table[5][4].type, RegisterRule.OFFSET)
+        self.assertEqual(decoded_FDE.table[5][4].arg, -12)
+
     def test_describe_CFI_instructions(self):
         # The data here represents a single CIE 
         data = ('' +