def euclidExtended(a, b):
  if b == 0:
    return a, 1, 0
  dd, xx, yy = euclidExtended(b, a % b)
  d, x, y = dd, yy, xx - int(a / b) * yy
  return d, x, y

def euclid(a, b):
  while b != 0:
    r = a % b
    a = b
    b = r
  return a

segment .text
  global easter_asm

;typedef struct {
;  unsigned short d;
;  unsigned short m;
;} Date;

;void easter_asm(unsigned short Y, Date *d)
;   computes the Easter date for the year Y and stores it in d
;
;Parameters
;   Y - the year
;   d - the Date struct in which to store the result

%define d [ebp + 12]
%define Y [ebp + 8]
easter_asm:
  enter 0, 0
  sub esp, 28
  %define G [ebp - 4]
  %define C [ebp - 8]
  %define X [ebp - 12]
  %define Z [ebp - 16]
  %define D [ebp - 20]
  %define E [ebp - 24]
  %define N [ebp - 28]

  ; int G = (Y % 19) + 1;
  xor edx, edx
  mov eax, Y
  mov ebx, 19
  div ebx
  inc edx
  mov G, edx

  ; int C = (int)(Y / 100) + 1;
  xor edx, edx
  mov eax, Y
  mov ebx, 100
  div ebx
  inc eax
  mov C, eax

  ; int X = 3 * C / 4 - 12;
  xor edx, edx
  mov eax, C
  mov ebx, 4
  div ebx
  mov ebx, 3
  mul ebx
  sub eax, 12
  mov X, eax

  ; int Z = (8 * C + 5) / 25 - 5;
  xor edx, edx
  mov eax, C
  mov ebx, 8
  mul ebx
  add eax, 5
  mov ebx, 25
  div ebx
  sub eax, 5
  mov Z, eax

  ; int D = 5 * Y / 4 - X - 10;
  xor edx, edx
  mov eax, Y
  mov ebx, 5
  mul ebx,
  mov ebx, 4
  div ebx
  sub eax, X
  sub eax, 10
  mov D, eax

  ; int E = (11 * G + 20 + Z - X) % 30;
  mov eax, G
  mov ebx, 11
  mul ebx
  add eax, 20
  add eax, Z
  sub eax, X
  xor edx, edx
  mov ebx, 30
  div ebx
  mov E, edx

  cmp dword E, 24
  jne after_e1
  inc dword E
  jmp after_e2
after_e1:
  cmp dword E, 25
  jne after_e2
  cmp dword G, 11
  jle after_e2
  inc dword E
after_e2:

  ; int N = 44 - E;
  mov eax, 44
  sub eax, E
  mov N, eax

  cmp dword N, 21
  jge after_n
  add dword N, 30
after_n:
  ; N = N + 7 - ((D + N) % 7);
  mov eax, N
  add eax, D
  xor edx, edx
  mov ebx, 7
  div ebx
  add dword N, 7
  sub N, edx

  mov eax, d

  ; N is the nuber of day from March 1 to easter. Check if easter is in April.
  cmp dword N, 31
  jle in_march
  mov bl, N
  sub bl, 31
  mov [eax], bl
  mov word [eax + 2], 4
  jmp quit
in_march:
  mov bl, N
  mov [eax], bl
  mov word [eax + 2], 3
quit:
  leave
  ret

void isort_c(unsigned *a, int n) {
  int k;
  for (k = 1; k < n; ++k) {
    int key = a[k];
    int i = k - 1;
    while ((i >= 0) && (key < a[i])) {
      a[i + 1] = a[i];
      --i;
    }
    a[i + 1] = key;
  }
}

; void isort(int *a, int n)
;   sorts the first n elements of a
;
; Parameters
;   a - pointer to the array
;   n - number of elements to sorts

%define a [ebp + 8]
%define n [ebp + 12]
isort:
  enter 0, 0
  pusha

  mov ecx, 1
  for:
    mov ebx, ecx
    imul ebx, 4
    add ebx, a
    mov ebx, [ebx]

    mov edx, ecx
    dec edx

    while:
      cmp edx, 0
      jl while_quit

      mov eax, edx
      imul eax, 4
      add eax, a

      cmp ebx, [eax]
      jge while_quit

      mov esi, [eax]

      mov dword [eax + 4], esi

      dec edx
      jmp while
    while_quit:

    mov [eax], ebx

    inc ecx
    cmp ecx, n
    jl for

  popa
  leave
  ret

void XORSwap(void *x, void *y)
{
   *x ^= *y;
   *y ^= *x;
   *x ^= *y;
}

unsigned bit_count(unsigned x) {
    unsigned n;
    for (n = 0; x; n++)
        x &= x-1;
    return n;
}