path: root/quine.asm

; 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 $?
;
; ***WARNING*** this version leaves the error message scrolled off the top of
; the screen and you see stale output
; fasmg quine.asm quine && ./quine > quine2; echo "exit code:" $?; echo; hexdump -C quine; echo; hexdump -C quine2; cmp quine quine2; echo; echo "compare:" $?
; ZydisDisasm -64 quine
;
; 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: $?
;
; 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/


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




org 0x08000000


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
elf_header_size = $ - elf_header

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?
program_header_entry_size = $ - program_header

load_origin = 0x08000000


;;; 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, load_origin
  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, load_origin       ; 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 = $ - $$