#  _   _                 _                 ____             _
# | \ | |_   _ _ __ ___ | |__   ___ _ __  / ___|  ___  _ __| |_ ___ _ __
# |  \| | | | | '_ ` _ \| '_ \ / _ \ '__| \___ \ / _ \| '__| __/ _ \ '__|
# | |\  | |_| | | | | | | |_) |  __/ |     ___) | (_) | |  | ||  __/ |
# |_| \_|\__,_|_| |_| |_|_.__/ \___|_|    |____/ \___/|_|   \__\___|_|
#
# By Peter Severin Rasmussen

.section .data
file_stat: .space 144   # Size of the fstat struct

.section .text
.globl _start
_start:

    # Note: xor register, register will be used to set register equal to 0
    #       as it results in a smaller binary

    #################
    #  File Reader  #
    #################

    # Strategy
    # --------
    #
    # Perform the following sequence of syscalls to read the file:
    #
    #           In                 Syscall                   Out
    # file path (from stack) ->     open    ->  fd
    # fd                     ->     fstat   ->  filesize
    # filesize               ->     brk     ->  file buffer pointer to allocated memory
    # (fd, filesize, f ptr)  ->     read    ->  Jackpot! (Data in buffer)
    # And of course close the file to be nice.

    # Registers
    # ---------
    #
    # r13       # fd
    # r14       # filesize
    # r15       # file buffer pointer

    # Open file
    mov $2, %rax         # Syscall 2 tells Linux to open
    mov 16(%rsp), %rdi   # The address of the file path is in the stack (argument)
    mov $2, %rsi         # Flags - According to header files read-only is 2
    xor %rdx, %rdx       # Access mode 0 - Read
    syscall              # File descriptor (fd) or error will be in rax

    mov %rax, %r13       # Save fd, so we don't lose it

    # Get file stat
    mov $5, %rax         # Syscall 5 - Fstat
    mov %r13, %rdi       # File descriptor as first argument
    mov $file_stat, %rsi # Use reserved space for the stat struct
    syscall              # file_stat struct should be filled with data

    # Get file size
    mov $file_stat, %rbx
    mov 48(%rbx), %rax    # Position of size in the struct

    mov %rax, %r14        # Save filesize

    # Get current end of heap
    mov $12, %rax  # Syscall 12 - Brk
    xor %rdi, %rdi # Allocate 0 bytes, i.e. get current end of heap
    syscall        # End of heap will be in rax

    mov %rax, %r15 # Save current end of heap as file pointer

    # Allocate buffer for file
    add %r14, %rax # Add filesize to file pointer
    mov %rax, %rdi # Set file pointer as parameter
    mov $12, %rax  # Syscall 12 - Brk. Allocates up till file pointer
    syscall


    # Read file
    xor %rax, %rax   # Syscall 0 - Read
    mov %r13, %rdi   # Load fd
    mov %r15, %rsi   # Where to put the read data
    mov %r14, %rdx   # How much to read
    syscall          # Allocated memory should now be filled with data

    # Close file
    mov $3, %rax     # Syscall 3 - Close
    mov %r13, %rdi   # Get file descriptor from where we saved it
    syscall


    #################
    # Count numbers #
    #################

    # Strategy
    # --------
    #
    # Go through every character and check if it is 10 (\n)
    # If yes, increment a counter
    # Furthermore, allocate memory for the parsed numbers.
    # The new buffer must be 8 times as big as the number of counted newlines,
    # because every number uses 64-bits = 8 bytes.

    # Registers
    # ---------
    #
    xor %rax, %rax  # Offset in file buffer
    xor %rbx, %rbx  # Char currently being read
    xor %rcx, %rcx  # Number counter
    # r12           # Number counter (saved for later)
    # r13           # Address of number buffer
    # r15           # Address of file buffer

num_count:                  # Go through every char and compare it with 10 ('\n')
    movb (%r15, %rax), %bl  # Load current byte we are at
    cmp $10, %rbx           # Compare it
    jne not_newline_count   # Skip increment of counter if not equal to 10
    inc %rcx                # Otherwise increment
not_newline_count:          #
    inc %rax                # Move to next byte
    cmp %r14, %rax          # Are we at the end? (Using filesize to determine)
    jle num_count           # If not, loop again

    mov %rcx, %r12 # Save the count for later
    imul $8, %rcx  # Find the actual size of the buffer (every entry is 64-bit)

    # Allocate another buffer
    # that holds the actual numbers

    # Calculate current end of heap (who needs syscalls anyway?)
    mov %r15, %rax # File buffer address
    add %r14, %rax # Add filesize
    # Voila!

    mov %rax, %r13 # Save current end of heap as number buffer

    # Allocate buffer for numbers
    add %rcx, %rax # Add number counter * 8 to end of heap to get end address
    mov %rax, %rdi # Set end address as parameter
    mov $12, %rax  # Syscall 12 - Brk (Allocate)
    syscall


    #############
    #  Parsing  #
    #############

    # Strategy
    # --------
    #
    # Parsing algorithm:
    # - Start result at 0
    # - Every time we read a non-newline char, shift result left in base 10 (mult by 10).
    # - Convert char to integer by subtracting 48
    # - Add converted integer to result
    # - Repeat
    # When reading newline char, we have parsed a number, so we save it and move to next
    # number in number buffer.

    # Registers
    # ---------
    #
    xor %rax, %rax  # Offset in file buffer
    xor %rbx, %rbx  # Char currently being read
    xor %rcx, %rcx  # Offset in number buffer
    xor %rdx, %rdx  # Current parser result
    # r12           # Size of number buffer
    # r13           # Address of number buffer
    # r14           # Size of file buffer
    # r15           # Address to file buffer

parse:                      # Go through every char again and compare it with 10 ('\n')
    xor %rbx, %rbx          # Clear rbx, just to be on the safe side
    movb (%r15, %rax), %bl  # Load current byte we are at
    cmp $10, %rbx           # Compare it
    je parse_newline        # If 10, go to newline routine. Else:

    sub $48, %bl            # Convert char to actual integer
    imul $10, %rdx          # Multiply the current result with 10 (shift left in base 10)
    add %rbx, %rdx          # Add converted integer to the result

    jmp parse_end           # Jump over the newline routine

parse_newline:              # Newline routine:
    mov %rdx, (%r13,%rcx,8) # Save current parser result
    xor %rdx, %rdx          # Reset parser result
    inc %rcx                # Move to the next number in number buffer

parse_end:                  # Last part of parse loop:
    inc %rax                # Move to next byte
    cmp %r14, %rax          # Are we at the end? (Using filesize to determine)
    jle parse               # If not, repeat


    ##########
    #  Sort  #
    ##########

    # Strategy
    # --------
    #
    # For sorting, we will use Gnome sort as it is one of the simplest
    # sorting algorithms and we strive for smallest binary.
    #
    # GnomeSort(A)
    #   n = A.length
    #   i = 0
    #   while i < n do
    #     if i = 0 or A[i-1] <= A[i] then
    #       i = i + 1
    #     else
    #       swap A[i-1] and A[i]
    #       i = i - 1

    # Registers
    # ---------
    #
    # rax           # Content of (%r13, %r8, 8)   - A[i]
    # rbx           # Content of -8(%r13, %r8, 8) - A[i-1]
    xor %r8, %r8    # i - Offset in number buffer
    #xor %rbp, %rbp # Number of comparisons - If someone asks: No I did not use the stack base pointer to count comparisons. Ehm. Nope.
    # r12           # Count of numbers in number buffer
    # r13           # Number buffer

gnome_sort_loop:
    cmp $0, %r8                 # If i = 0
    je gnome_sort_inc           # Increment i
    mov (%r13, %r8, 8), %rax    # A[i]
    mov -8(%r13, %r8, 8), %rbx  # A[i-1]
    #inc %rbp                   # Increment # of comparisons - Your eyes must be deceiving you
    cmp %rax, %rbx              # If A[i-1] <= A[i] (compare unsigned)
    jbe gnome_sort_inc          # Increment i
    jmp gnome_sort_swap         # Else swap and decrement i

gnome_sort_inc:                 # Increment i and jump to loop end
    inc %r8
    jmp gnome_sort_loop_end

gnome_sort_swap:                # Swap A[i] and A[i-1] and decrement i
    mov %rbx, (%r13, %r8, 8)
    mov %rax, -8(%r13, %r8, 8)
    dec %r8

gnome_sort_loop_end:
    cmp %r12, %r8               # Are we at the end?
    jl gnome_sort_loop          # If not, repeat loop




    ###########
    #  Print  #
    ###########

    # Strategy
    # --------
    #
    # First, allocate 21 bytes to store any 64-bit number in base 10 => 20 bytes + 1 byte for newline
    #
    # Print algorithm:
    # - Convert number back to characters
    # - and fill the following space with the characters backwards up to MSD:
    #   _ _ _ ... _ _ _ \n         |     E.g. _ _ _ ... 3 5 1 \n
    # - Call write syscall and write from MSD to \n
    # - Repeat
    #
    # Convert algorithm:
    # - Divide n by 10
    # - Remainder r is next digit to write (0 <= r < 10)
    # - Add 48 to get to ascii char
    # - When quotient is 0, we are done
    #
    # Register list follow

    mov %r13, %r15 # Address of number buffer
    mov %r12, %r14 # Copy count of numbers, so we can multiply without destroying the original
    imul $8, %r14  # Multiply by 8 to get actual size of buffer
    add %r14, %r15 # Add size of buffer to get to the end of heap
    mov %r15, %rdi # Store in rdi
    add $21, %rdi  # Add 21 to allocate 21 bytes (needed to represent any 64-bit number + newline char)
    mov $12, %rax  # Syscall 12 - Brk (Allocate)
    syscall

    movb $10, (%rdi) # Insert newline (\n) at the end

    # Registers
    # ---------
    #
    # rax           # Number currently being printed
    xor %r9, %r9    # Offset in number buffer
    # r8            # Offset in output buffer
    mov $10, %r10   # Divisor
    # r12           # Number of numbers in number buffer
    # r13           # Address of number buffer
    # r14           # Size of number buffer
    # r15           # Address of output buffer


print_loop:
    mov $20, %r8            # Reset offset in output buffer
    mov (%r13,%r9,8), %rax  # Load number to print

convert_back:
    xor %rdx, %rdx          # When dividing, make sure there is no garbage in rdx
    div %r10                # Divide number by 10. Quotient in rax, remainder in rdx
    add $48, %rdx           # Remainder (in rdx) is the number to print. We convert it to a char
    movb %dl, (%r15, %r8)   # Place char in the buffer starting from the end
    dec %r8                 # Step backwards through the output buffer
    cmp $0, %rax            # If quotient is 0, we are done
    jne convert_back        # If not, we repeat

    inc %r8                 # Move from nothingness to most significant digit

    mov $1, %rax            # Syscall 1 - Write
    mov $1, %rdi            # File descriptor 1 - Std out
    mov %r15, %rsi          # The buffer to write starts at
    add %r8, %rsi           #  r15 + offset
    mov $22, %rdx           # The chars to read can also be calculated using
    sub %r8, %rdx           #  22 - offset + 1 (to make interval inclusive) + 1 (\n)
    syscall

    inc %r9                 # Move to next number
    cmp %r12, %r9           # If there are still numbers left
    jl print_loop           # We repeat


    ##########
    #  Exit  #
    ##########

    mov $60, %rax   # Syscall 60 - Exit
    xor %rdi, %rdi  # Error code 0
    syscall         # Exit gracefully