path: root/quine.asm

;;; Workflow tips:
;;;
;;; Currently, this is not yet fully self-hosting; it is based on
;;; flatassembler[1]. A minimal command to build and run it is:
;;;
;;; fasmg quine.asm quine && chmod 755 quine && ./quine; echo $?
;;;
;;; A workflow you may wish to use for debugging is:
;;;
;;; rm quine2; fasmg quine.asm quine && ./quine > quine2; echo "exit code:" $?; echo; hexdump -C quine; echo; hexdump -C quine2; echo; cmp quine quine2 ; echo cmp: $?
;;;
;;; The reason this removes the old one first is that otherwise, there's a
;;; risk the error message will be scrolled off the top of the screen and
;;; you'll see stale output and not realize.
;;;
;;; You may also wish to do:
;;;
;;; objdump --disassemble quine
;;; ZydisDisasm -64 quine
;;;
;;; This relies on GNU binutils, and on zydis, respectively.
;;;
;;; [1] https://flatassembler.net/


;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Assembly language ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;; Before doing any actual code, we define macros for writing x86-64 assembly
;;; language. This is built from scratch, relying only on flatassembler's
;;; built-in semantics. No include files of any kind are used for it.

macro rex.0
  db 0x40
end macro

macro rex.w
  db 0x48
end macro

macro rex.xb
  db 0x43
end macro

macro modrm mod, reg, rm
  assert mod >= 0 & mod < 4
  assert reg >= 0 & reg < 8
  assert rm >= 0 & rm < 8
  db (mod shl 6) or (reg shl 3) or rm
end macro

macro sib scale, index, base
  assert scale >= 0 & scale < 4
  assert index >= 0 & index < 8
  assert base >= 0 & index < 8
  db (scale shl 6) or (index shl 3) or base
end macro

macro opcodereg opcode, reg
  assert opcode >= 0 & opcode < 256 & opcode and 7 = 0
  assert reg >= 0 & reg < 8
  db opcode or reg
end macro

macro qwordreg result, register
  match =rax?, register
    result = 0
  else match =rcx?, regiser
    result = 1
  else match =rdx?, register
    result = 2
  else match =rbx?, register
    result = 3
  else match =rsp?, register
    result = 4
  else match =rbp?, register
    result = 5
  else match =rsi?, register
    result = 6
  else match =rdi?, register
    result = 7
  else
    assert 0
  end match
end macro


; TODO what register size does this use?
macro mov.b target, source
  match =rax?, target
    db 0xB8
    dd source
  else match =rdi?, target
    db 0xBF
    dd source
  else
    assert 0
  end match
end macro


; TODO what register size does this use?
macro mov.dreg.dimm target, source
  rex.w
  db 0xC7
  qwordreg reg, target
  modrm 3, 0, reg
  dd source
end macro


macro mov.qreg.qimm target, source
  rex.w
  qwordreg treg, target
  opcodereg 0xB8, treg
  dq source
end macro


macro mov.qreg.qreg target, source
  qwordreg treg, target
  qwordreg sreg, source
  rex.w
  db 0x89
  modrm 3, sreg, treg
end macro


; TODO what register size does this use?
macro add.b target, source
  match =rax, target
    rex.w
    db 0x83
    modrm 3, 0, 0
    db source
  else
    assert 0
  end match
end macro


macro add.q target, source
  db 0x01
  qwordreg treg, target
  qwordreg sreg, source
  modrm 3, sreg, treg
end macro


; TODO what register size does this use?
macro sub.b target, source
  match =rsp, target
    rex.w
    db 0x83
    modrm 3, 5, 4
    db source
  else
    assert 0
  end match
end macro


; Move from an 8-bit immediate value, to a location relative to a 64-bit
; register, with an 8-bit displacement and no indexing.
;
; This uses opcode 0xC6, which has w = 0. Since we run in 64-bit mode, that
; makes the operand size 8 bits, regardless of the current operand-size
; attribute. [Intel] volume 2D, section B.1.43, table B-6.
macro mov.rel.b target, offset, source
  match =rsp, target
    db 0xC6
    modrm 1, 0, 4
    sib 0, 0, 4
    db offset
    db source
  else
    assert 0
  end match
end macro

; Move from a 16-bit immediate value, to a location relative to a 64-bit
; register, with an 8-bit displacement and no indexing.
;
; This uses opcode 0xC7, which has w = 1. We run in 64-bit mode, so that gives
; us an operand size of 32 bits by default. [Intel] volume 1, section 3.6.1,
; table 3-4. We want a 16-bit operand, so we use the operand-size prefix,
; 0x66, and we leave REX.W unset.
macro mov.rel.w target, offset, source
  match =rsp, target
    db 0x66
    db 0xC7
    modrm 1, 0, 4
    sib 0, 4, 4
    db offset
    dw source
  else
    assert 0
  end match
end macro

; Move from a 32-bit immediate value, to a location relative to a 64-bit
; register, with an 8-bit displacement and no indexing.
;
; This uses opcode 0x67, which has w = 1. We run in 64-bit mode, so that gives
; us an operand size of 32 by default. [Intel] volume 2D, section B.1.43,
; table B-6. This is what we want, so we leave it.
macro mov.rel.d target, offset, source
  match =rsp, target
    db 0xC7
    modrm 1, 0, 4
    sib 0, 4, 4
    db offset
    dd source
  else
    assert 0
  end match
end macro

; Move from a 64-bit register, to a 64-bit location relative to a 64-bit
; register, with an 8-bit displacement and no indexing.
;
; This uses opcode 0x89.
macro mov.rel.q target, offset, source
  match =rsp, target
    qwordreg sreg, source
    rex.w
    db 0x89
    modrm 1, sreg, 4
    sib 0, 4, 4
    db offset
  else
    assert 0
  end match
end macro

; Move from a 32-bit immediate value, to a 64-bit location relative to a
; 64-bit register, with an 8-bit displacement and no indexing.
;
; Note that there is no instruction to move a 64-bit immediate to memory.
;
; This uses opcode 0xC7, which has w = 1. We run in 64-bit mode, so that
; gives us an operand size of 32 by default. [Intel] volume 2D,
; section B.1.43, table B-6. We want a 64-bit operand, so we use the REX.W
; prefix, 0x48.
macro mov.rel.q.d target, offset, source
  match =rsp, target
    rex.w
    db 0xC7
    modrm 1, 0, 4
    sib 0, 4, 4
    db offset
    dd source
  else
    assert 0
  end match
end macro

macro syscall
  db 0x0F, 0x05
;        0f                      two-byte escape
;           05                   syscall ^ o64
end macro




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Executable file format ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;; Before we get into the meat of the program, we do a lot of ELF-specific
;;; stuff to ensure that our output is in a format Linux knows how to run.
;;;
;;; First, we set the origin to load at. This is arbitrary, but it can't be
;;; zero. We tell flatassembler about it because it's used in label
;;; calculations; we can reference it as $$ any time we need it in future.
org 0x08000000

;;;
;;; Second, we output ELF's top-level file header.
;;;
elf_header:
  ; * denotes mandatory fields according to breadbox
  db 0x7F, "ELF"                 ; *magic number
  db 2                           ; 64-bit
  db 1                           ; little-endian
  db 1                           ; ELF header format version 1
  db 0                           ; System-V ABI
  db 8 dup 0                     ; (padding)

  dw 2                           ; *executable
  dw 0x3E                        ; *Intel x86-64
  dd 1                           ; ELF format version

  dq _start                      ; *entry point
  dq program_header - $$         ; *program header offset
  dq 0                           ; section header offset
  dd 0                           ; processor flags
  dw elf_header_size
  dw program_header_entry_size   ; *
  dw 1                           ; *number of program header entries
  dw 0                           ; section header entry size
  dw 0                           ; number of section header entries
  dw 0                           ; section name string table index
; Save a copy of the size of this chunk for our future reference, by comparing
; the current posiion to the label above.
elf_header_size = $ - elf_header

;;;
;;; Third, immediately after the ELF file header, we output ELF's program
;;; header, which lists the memory regions ("segments") we want to have and
;;; where we want them to come from. We list just a single region, which is
;;; the entire contents of the ELF file from disk.
;;;
;;; It would be more typical to have separate code and data segments, and
;;; perhaps a stack or heap, but this keeps things simple. We do have a little
;;; stack space available, though we don't explicitily request any; the kernel
;;; allocates it for us as part of exec() so that it can pass us argc and argv
;;; (which we ignore). That stack space will be at a random address, different
;;; every time, because of ASLR; that's a neat security feature, so we leave
;;; it as-is.
;;;
program_header:
  dd 1                           ; *"loadable" segment type
  dd 0x05                        ; *read+execute permission
  dq 0                           ; *offset in file
  dq $$                          ; *virtual address
                                 ;   required, but can be anything, subject to
                                 ;   alignment
  dq 0                           ; physical address (ignored)
  dq file_size                   ; *size in file
  dq file_size                   ; *size in memory
  dq 0                           ; segment alignment
                                 ;   for relocation - will we be ASLR'd?
; Save the size of this chunk, as well.
program_header_entry_size = $ - program_header


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Implementation strategy ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;;   We assemble the entire file contents in a stack-allocated buffer.
;;; We avoid using the stack for any other purpose. When the file is fully
;;; assembled, we output it.
;;;
;;;   The assembly proceeds in several chunks - ELF header, program header,
;;; etc. Each chunk extends the buffer as per its own needs, by adjusting
;;; the stack pointer. All chunks also update a running total file size,
;;; which refers to how many bytes have actually been populated, not to the
;;; size of the buffer.
;;;
;;; Register usage:
;;;
;;; * rdx holds the total used file size so far. During hand-off between
;;;   chunks, this size must be equal to the buffer size; within a chunk it
;;;   may be less.
;;;
;;; * rsp points to the bottom of the buffer.
;;;
_start:
  ;;;
  ;;; Initialize registers
  ;;;
  mov.dreg.dimm rdx, 0                     ; store running file size here
  sub.b rsp, 0xFF                          ; reserve stack space

  ;;;
  ;;; ELF header
  ;;;
  mov.rel.d rsp, 0x00, 0x7F bappend "ELF"  ; magic number
  mov.rel.b rsp, 0x04, 2                   ; 64-bit
  mov.rel.b rsp, 0x05, 1                   ; little-endian
  mov.rel.b rsp, 0x06, 1                   ; ELF header format version 1
  mov.rel.b rsp, 0x07, 0                   ; System-V ABI
  mov.rel.q.d rsp, 0x08, 0                 ; (padding)

  mov.rel.w rsp, 0x10, 2                   ; executable
  mov.rel.w rsp, 0x12, 0x3E                ; Intel x86-64
  mov.rel.d rsp, 0x14, 1                   ; ELF format version

  ; Compute the entry pointer.
  mov.qreg.qimm rax, $$
  add.b rax, 120
  mov.rel.q rsp, 0x18, rax                 ; entry point

  mov.rel.q.d rsp, 0x20, 64                ; program header offset
    ; We place the program header immediately after the ELF header. This
    ; offset is from the start of the file.
  mov.rel.q.d rsp, 0x28, 0                 ; section header offset
  mov.rel.d rsp, 0x30, 0                   ; processor flags
  mov.rel.w rsp, 0x34, 64                  ; ELF header size
  mov.rel.w rsp, 0x36, 56                  ; program header entry size
  mov.rel.w rsp, 0x38, 1                   ; number of program header entries
  mov.rel.w rsp, 0x3a, 0                   ; section header entry size
  mov.rel.w rsp, 0x3c, 0                   ; number of section header entries
  mov.rel.w rsp, 0x3e, 0                   ; section name string table index

  ; Add the size of the ELF header to the running total
  mov.dreg.dimm rax, 0x40
  add.q rdx, rax

  ;;;
  ;;; Program header
  ;;;
  mov.rel.d rsp, 0x40, 1                   ; "loadable" segment type
  mov.rel.d rsp, 0x44, 0x05                ; read+execute permission
  mov.rel.q.d rsp, 0x48, 0                 ; offset in file
  mov.rel.q.d rsp, 0x50, $$                ; virtual address
    ; required, but can be anything, subject to alignment
  mov.rel.q.d rsp, 0x58, 0                 ; physical address (ignored)

  ; Fill in 0 as the file size for now, to avoid unitialized memory.
  mov.rel.q.d rsp, 0x60, 0                 ; size in file
  mov.rel.q.d rsp, 0x68, 0                 ; size in memory

  mov.rel.q.d rsp, 0x70, 0                 ; segment alignment
    ;   for relocation - will we be ASLR'd?

  ; Add the size of the program header to the running total
  mov.dreg.dimm rax, 0x38
  add.q rdx, rax

  ; Add the guessed, wrong size of the program

  ;;; Hardcode the size of the actual code chunk, since we don't yet have a
  ;;; way to generate it.
  ;;;
  ;;; TODO of course, really we want to for-real track this
  mov.qreg.qimm rax, 0x15a
  add.q rdx, rax

  ;;;
  ;;; Go back and fill in the file size now that we know it.
  ;;;
  mov.rel.q rsp, 0x60, rdx                 ; size in file
  mov.rel.q rsp, 0x68, rdx                 ; size in memory

  ;;;
  ;;; The buffer is ready; output the file.
  ;;;

  ; write() from stack-allocated buffer
  mov.b rax,1
  mov.qreg.qimm rdi, 1
  mov.qreg.qreg rsi, rsp
  mov.qreg.qimm rdx, 0x78
  syscall

  ; write() the machine code by using self-reference
  ;
  ; TODO do this in a "real" quine way
  mov.b rax, 1
  mov.qreg.qimm rdi, 1
  mov.qreg.qimm rsi, elf_header + 0x78
  mov.qreg.qimm rdx, file_size - 0x78
  syscall

  ;;;
  ;;; Clean up.
  ;;;

  ; exit()
  mov.b rax, 60
  mov.b rdi, 0
  syscall

file_size = $ - $$