## August 25, 2014

### Knight's tour in 8086 assembly (MASM)

Almost 20 years ago I wrote an assembly code to solve Knight’s tour problem as my C solution was too slow. The code was lost on a backup disk and I’ve accidentally found it over the weekend. If you have MASM you can make a binary and test it.

```.8086
.MODEL TINY

CR      EQU     0dh
LF      EQU     0ah
SPACE   EQU     20H

.DATA?
table           dw      81 DUP (?)      ; Worst case of 9x9 board.
table_end       dw      ?               ; Offset of the last element in
; the table.
jump            dw      8 DUP (?)

;       (2*N+1)*2  - 0
;       (N+2)*2    - 1      7 0      COLUMN
;       (-N+2)*2   - 2     6   1            R
;       (-2*N+1)*2 - 3       x              O
;       (-2*N-1)*2 - 4     5   2            W
;       (-N-2)*2   - 5      4 3
;       (N-2)*2    - 6
;       (2*N-1)*2  - 7
; jump   --     Movement from the current position as
;               a function of the move type.

N               dw      ?       ; Table size.
NN              dw      ?       ; N*N
N2              dw      ?       ; 2*N
N_char          db      ?       ; N as ASCII.

;       Register usage:
;       SI - current field.
;       DI - next field.
;       BX - movement type.
;       DX - info on the current field:
;               DH - allowed moves
;               DL - how many moves are tried from this field.
;       AX - info on the next field:
;               AH - allowed moves
;               AL - how many moves are tried from this field.

.DATA
db      'Author '
author          db      'http://www.aleksa.org'
table_size      db      CR, LF, 'Table size [3..9] > \$'
x_pos           db      CR, LF, 'row > \$'
y_pos           db      CR, LF, 'column  > \$'
analyzing_board db      CR, LF, 'Analyzing the board...',CR,LF,'\$'
nosolution      db      CR, LF, 'No solution.\$'

.STACK 1024

.CODE
.STARTUP
mov     ah, 09h
mov     dx, offset author
int     21h             ; Display 'Table size [3..9] > '
mov     ah, 01h
int     21h             ; DOS call to read a char to AL.
cmp     al, '3'
jb      error           ; Exit if not in [3, 9] range.
cmp     al, '9'
jbe     ok_N
error:  jmp     finish
ok_N:   mov     N_char, al
and     ax, 000fh       ; ASCII number -> bin number.
mov     N, ax

shl     ax, 1
mov     N2, ax          ; N2 <- N*2
mov     ax, N
mul     al
mov     NN, ax          ; NN <- N*N

mov     table_end, offset table
dec     ax              ; AX <- N*N-1
shl     ax, 1           ; Every table element is 2 bytes.
add     table_end, ax   ; table_end has the offset of the last element
; in the table.

;---    Moves initialization.

mov     di, offset jump

mov     ax, N2
inc     ax
shl     ax, 1           ; (2*N+1)*2
mov     [di], ax        ; Move 0.
neg     ax
mov     [di+8], ax      ; Move 4.
add     di, 2           ; Point to the next element in the move list.

mov     ax, N
shl     ax, 1           ; (N+2)*2
mov     [di], ax        ; Move 1.
neg     ax
mov     [di+8], ax      ; Move 5.
add     di, 2           ; Point to the next element in the move list.

mov     ax, N
neg     ax
shl     ax, 1           ; (-N+2)*2
mov     [di], ax        ; Move 2.
neg     ax
mov     [di+8], ax      ; Move 6.
add     di, 2           ; Point to the next element in the move list.

mov     ax, N2
neg     ax
inc     ax
shl     ax, 1           ; (-2*N+1)*2
mov     [di], ax        ; Move 3.
neg     ax
mov     [di+8], ax      ; Move 7.

;---    Board initialization, mark illegal moves.

mov     di, offset table; DI points to the table start.
push    di
xor     ax, ax
mov     cx, NN
cld
rep     stosw                   ; Fill the table with 0s.
pop     di              ; Start from the beginning.
mov     ax, 3c00h       ; Illegal moves 2,3,4 and 5 for the first
mov     cx, N           ; column.
rep     stosw
mov     ax, 1800h       ; Illegal moves 3 and 4 for the second column.
mov     cx, N
rep     stosw
mov     di, table_end
mov     ax, 0c300h      ; Illegal moves 0,1,6 and 7 for the last
mov     cx, N           ; row.
std
rep     stosw
mov     ax, 8100h       ; Illegal moves 0 and 7 for the next to last
mov     cx, N           ; column.
rep     stosw
mov     di, offset table
mov     ax, 0f00h       ; Illegal moves 4, 5, 6 and 7 for the first
mov     cx, N           ; row.
lab1:   or      [di], ax
loop    lab1
mov     di, offset table+2
mov     ax, 0600h       ; Illegal moves 5 and 6 for the second row.
mov     cx, N
lab2:   or      [di], ax
loop    lab2
mov     di, table_end
mov     ax, 0f000h      ; Illegal moves 0,1,2 and 3 for the last row.
mov     cx, N
lab3:   or      [di], ax
sub     di, N2
loop    lab3
mov     di, table_end
sub     di, 2
mov     ax, 6000h       ; Illegal moves 1 and 2 for the last row.
mov     cx, N
lab4:   or      [di], ax
sub     di, N2
loop    lab4

;---    Set starting position - first column, then row.

mov     ah, 09h         ; DOS call to display the message.
mov     dx, offset x_pos
int     21h             ; 'column >'
mov     ah, 01h         ; DOS call to read a character into AL.
int     21h
cmp     al, '1'
jb      lab5            ; Exit if not within bounds.
cmp     al, N_char      ; Exit if greater than table size.
ja      lab5
mov     cl, al
mov     ah, 09h         ; DOS call to display the message.
mov     dx, offset y_pos
int     21h             ; 'row  >'
mov     ah, 01h
int     21h             ; DOS call to read a char to AL.
cmp     al, '1'
jb      lab5
cmp     al, N_char      ; Exit if greater than table size.
jbe     ok              ; Looks good.
lab5:   jmp     finish          ; As finish is more than 128 bytes away.
ok:     mov     ch, al          ; CH - row, CL - column.
mov     ah, 09h
mov     dx, offset analyzing_board
int     21h             ; 'Analyzing the board...'
and     cx, 0f0fh       ; Convert from ASCII to a number.
dec     cl              ; Subtract 1 to mark the right field.
dec     ch

;---    Set SI to point to the starting field.

mov     ax, N
mul     ch              ; AL <- row*N
xor     ch, ch
add     ax, cx          ; AL <- row*N + column
shl     ax, 1           ; and multiply everything by 2.
mov     si, offset table
add     si, ax          ; SI - now pointing to the starting position.
xor     bx, bx          ; BX <- 0
mov     dx, [si]        ; Put the info on the current field.
mov     dl, 1           ; Fields visited so far.

;---    Start filling the board.

mov     cx, NN          ; !!!
search: rol     dh, 1           ; Rotate left, MSB is in CF.
jc      nomove          ; Illegal move.
mov     di, si
add     di, jump[bx]    ; DI has the address of the next field.
mov     ax, [di]        ; Load it.
test    al, al          ; Is it taken?
jnz     nomove          ; Yes.
mov     [si], dx        ; No, store the old field,
push    si              ;
push    bx              ; and what was the last move from that field.
mov     si, di          ; Move the pointer to the new field.
mov     dh, ah          ; Illegal moves go to DH.
inc     dl              ; Increment the visited fields number.
cmp     dl, cl          ; Did you fill the board?
jne     search          ; No.
jmp     short print     ; Yes, print it.
nomove: add     bx, 2           ; Try the next move.
cmp     bx, 16          ; Have you tried all moves?
jb      search          ; No.
cmp     dl, 1           ; Are you back to the starting position?
je      sorry           ; Yes, then there is no solution.
xor     dl, dl
mov     [si], dx        ; Unmark the field.
pop     bx              ; What was the last move?
pop     si              ; Go back by one field.
mov     dx, [si]
jmp     short nomove

;--- Print the solution, but convert to ASCII first.

print : mov     [si], dx
mov     si, offset table
; CS already has N*N !!!
lab7:   mov     ax, [si]
aam
or      ax, 3030h       ; Convert to ASCII
mov     [si], ax
loop    lab7
mov     ah, 02h
mov     dl, CR
int     21h
mov     dl, LF
int     21h
mov     si, offset table
mov     cx, N
crt:    mov     dl, [si+1]
cmp     dl, '0'
jne     good
mov     dl, SPACE
good:   int     21h
mov     dl, [si]
int     21h
mov     dl, SPACE
int     21h
loop    crt
mov     dl, CR
int     21h
mov     dl, LF
int     21h
cmp     si, table_end
jg      finish
mov     cx, N
jmp     short crt
sorry:  mov     ah, 09h         ; Print that there is no solution.
mov     dx, offset nosolution
int     21h
finish: .EXIT 0

END
```

## August 10, 2014

### GoPacker

A year ago I was working on a server in Go that I wanted to be easy to deploy and move around. Go is great for providing you with one statically linked binary, but I also had few files that needed to be bundled with the code (CSS, JavaScript, images).

At that time I couldn't find a solution that would fit my needs so I wrote one: GoPacker. Hope you find this script useful.

## March 7, 2013

### Configure git to use a different tool for diffing

I don't like default `git diff` output: I prefer `vimdiff` or `tkdiff`. Here is a recipe that explains how to set up external diff.
Your basic `~/.gitconfig` should have `[diff]` section as in:
``````[user]
email = <your@email>
[color]
status = auto
diff = auto
branch = auto
interactive = auto
[core]
editor = vim
pager = less -FRSX
[diff]
[merge]
tool = vimdiff
``````
Create external `gittkdiff.sh` and make it executable (`chmod +x`):
``````#!/bin/sh

/usr/bin/tkdiff "\$2" "\$5" | cat
``````
For `vimdiff` use:
``````#!/bin/sh

/usr/bin/vimdiff "\$2" "\$5" | cat
``````

[Update - 08/10/2014]

Newer git can do this for you:
``````git config --global diff.tool tkdiff
git config --global merge.tool tkdiff
git config --global --add difftool.prompt false
``````

## March 4, 2013

### Replacing Python's positional arguments with keyword arguments

I was renaming a positional function argument named `id` (which was masking Python's built in function `id()`), but that broke the rest of the third party code. I've just discovered a very nasty language feature.

A function in Python that takes only positional arguments:

``````def foo(x, y):
print x ** y
``````

should be called as:

``````foo(2, 3)
``````

But when calling a function it is possible to use keyword arguments in place of the given positional arguments:

``````foo(2, y=3)
foo(x=2, y=3)
``````

Whoever wrote `foo()` counts it will always be called with positional arguments, but there is no way to prevent someone to use keyword calling style (`foo(2, y=3)`). If `foo()` arguments are renamed, e.g. to make it more readable:

``````def foo(base, exponent):
print base ** exponent
``````

the code using it will stop working:

``````>>> foo(x=2, y=3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: foo() got an unexpected keyword argument 'x'
``````

Positional function arguments should be and stay local, but that is not the case in Python. One could blame the programmer, but language should be able to prevent this problem. Never use keyword argument for a function that doesn't explicitly define one. This is a very nasty way to introduce bugs in otherwise very clean and safe code.

It goes the other way around: a function with keyword arguments can be called as if it was defined with positional arguments:

``````def hi(name="Nobody"):
print "Hi {}!".format(name)
``````

Usage:

``````>>> hi(name="Aleksa")
Hi Aleksa!
>>> hi("Aleksa")
Hi Aleksa!
``````

I'd prefer to see an error here, but it "does the right thing" in a Perl like fashion. Keyword to positional argument replacement is going to make your code less readable, but will not break it as when replacing positional for named arguments.

Python 3 changed things a bit, but didn't fix the problem. Having `*` between positional and keyword arguments ensures that keyword arguments are properly used:

``````def foo(x, *, y=None):
print("X: {}".format(x), end="\n")
print("Y: {}".format(y), end="\n")
``````
``````>>> foo(1, 2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: foo() takes 1 positional argument but 2 were given
>>> foo(1, y=2)
X: 1
Y: 2
``````

However, positional arguments can still be replaced with keyword arguments:

``````>>> foo(x=1, y=2)
X: 1
Y: 2
``````

Every function argument in Python is a hybrid global variable!

## March 2, 2013

### Python friendly .vimrc

```syn on
let python_highlight_builtins=1
au FileType python setlocal expandtab shiftwidth=4 softtabstop=4 colorcolumn=80 ai nu nowrap cul
```

`let python_highlight_builtins=1` enables coloring of reserved and built in functions in Python. It is going to make you aware when a variable name overrides a built in function (e.g. `id` or `type`). For details on other specific parameters see Python's wiki page on vim and "Secrets of tabs in vim."

```set foldmethod=indent
```

and you can open a fold with `zo`, close with `zc`, close all in the document with `zM` or open with `zR`.

To emulate PyCharm's variables highlighting under the cursor try this command:

```:autocmd CursorMoved * exe printf('match Search /\V\<%s\>/', escape(expand('<cword>'), '/\'))
```

## March 1, 2013

### Python resources

Useful material for mastering and using Python in the industry.

## Development Tools

• PyCharm: powerful Python and Django IDE — The best IDE for Python. You can be very productive in an editor, but PyCharm has nice tools to catch common errors and help refactor the code.

• Python Ecosystem — Basics of the Python ecosystem for web application development for developers who shift to Python from other platforms.

• pypy — A fast, compliant alternative implementation of the Python language (2.7.2).

## Useful Libraries

• python-gflags — Google command line flag is intended to be used in situations where a project wants to mimic the command-line flag handling of a C++ app that uses google-gflags, or for a Python app that, via swig or some other means, is linked with a C++ app that uses google-gflags.

• gevent for the Working Python Developer — The structure of this tutorial assumes an intermediate level knowledge of Python but not much else. No knowledge of concurrency is expected. The goal is to give you the tools you need to get going with gevent, help you tame your existing concurrency problems and start writing asynchronous applications today.

• pymox — A mock object framework for Python. Mox is based on EasyMock, a Java mock object framework.

• Django — A high-level Python Web framework that encourages rapid development and clean, pragmatic design.

• matplotlib — A 2D plotting library which produces publication quality figures in a variety of hardcopy formats and interactive environments across platforms.

• pydot — Allows to easily create both directed and non directed graphs from Python. You'd need to install GraphViz as well.

• Gnuplot.py — A Python package that interfaces to gnuplot, the popular open-source plotting program. It allows you to use gnuplot from within Python to plot arrays of data from memory, data files, or mathematical functions.

• SWIG — A software development tool that connects programs written in C and C++ with a variety of high-level programming languages. SWIG is used with different types of target languages including common scripting languages such as Perl, PHP, Python, Tcl and Ruby. Check out this tutorial that shows you how to interface with Python.

• SciPy — An open-source software for mathematics, science, and engineering. The SciPy library depends on NumPy, which provides convenient and fast N-dimensional array manipulation.

## Related Resources

• HTTP status codes cheat sheet — You will need this for web programming.

• Graphical vi-vim Cheat Sheet and Tutorial — I found vim to be good for editing Python, mainly because it can do copy-paste with proper indent adjustment (pasting with `]p` instead of `p`).

• git — Distributed version control system designed to handle everything from small to very large projects with speed and efficiency.