\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{ACME -- The Andrews-Curtiss Conjecture Move Enumerator}
\author{Timothy Daly}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{include}
We need [[stdio.h]] for the [[printf]] function.
<<include>>=
#include <stdio.h>

@
\section{Binary Buddy Storage Allocator}
The binary buddy storage allocation scheme relies on the fact that
memory is allocated in powers of 2. Thus we know that if we give out
a block of storage we can break it into two halves. 

Suppose a request comes in for a 4K block of storage. Suppose there
are no 4K blocks free. So we ask for an 8K block, split the result
into 2 4K blocks. The first 4K block we keep in the [[buddy]] array.
The second 4K block we give away to satisfy the request.

If the second 4K block gets returned and we have the first 4K block
we can combine the two one 8K block and return the newly combined
8K block.

If the second 4K block gets returned and the first one is out then
we just store it in the [[buddy]] array.

To allocate memory we index into the array by the log of the size
of the requested storage. We can compute this by shifting the number
of requested bytes by (n-1). Thus 
\begin{verbatim}
 1 byte is 0, 
 2 bytes is 1, 
 4 bytes is 2, 
 8 bytes is 3
\end{verbatim}
and so on.
If the entry is not zero then zero the array entry and 
return the address previously stored in the array.
If the entry is zero we recursively call the new function for the
next largest size block. 
\subsection{Buddy Array}
buddy is an array of addresses. The zeroth entry is the address
of either a block of free storage of the correct size or 0.
<<buddyarray>>=
char *buddy[] = {0, /*1*/
                 0, /*2*/
                 0, /*4*/
                 0, /*8*/
                 0, /*16*/
                 0, /*32*/
                 0, /*64*/
                 0, /*128*/
                 0, /*256*/
                 0, /*512*/
                 0, /*1024*1*/
                 0, /*1024*2*/
                 0, /*1024*4*/
                 0, /*1024*8*/
                 0, /*1024*16*/
                 0, /*1024*32*/
                 0, /*1024*64*/
                 0, /*1024*128*/
                 0, /*1024*256*/
                 0, /*1024*512*/
                 0  /*1024*1024*/};                 
int buddylength = 21;                   

@
\subsection{Print Buddy Array}
The [[printbuddy]] function dumps the buddy array contents. 
<<printbuddies>>=
void printbuddy()
{ static int I=0;
  int i = 0;
  int size = 1;
  printf("%d new:enter printbuddies\n",++I);
  for(i=buddylength; i>0; )
  { printf("new: buddy[%8d] = %x\n",size,buddy[--i]);
    size=size<<1;
  }
  printf("%d new:exit  printbuddies\n",I);
}

@
\subsection{Allocate a new block of storage}
<<newbuddy>>=
char *new(int size)
{ static int I=0;
  printf("%d new:enter %d bytes\n",++I,size);
  printbuddy();
  printf("%d new:exit\n",I);
}

@
\subsection{Binary Buddy Storage Allocator}
<<binarybuddy>>=
<<buddyarray>>
<<printbuddies>>
<<newbuddy>>
@
\section{main}
\subsection{main}
<<main>>=
int main(int argc, char *argv[])
{ printf("main:exit\n");
  new(4);
  printf("main:exit\n");
  return(0);
}

@
<<*>>=
<<include>>
<<binarybuddy>>
<<main>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}