aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorlloyd <[email protected]>2006-08-20 21:51:29 +0000
committerlloyd <[email protected]>2006-08-20 21:51:29 +0000
commit500a0df7d83f9e062b7f35ecc5134546c4742d75 (patch)
treeeaf75f091058ce6a3c59c9dd2835cdcf80cbb5a2
parentc5e1e02c8fff058cf7708ce14fdb2e20fe588528 (diff)
Started working on the internals documentation again
-rw-r--r--doc/internals.tex163
-rw-r--r--doc/misc/internals.tex153
2 files changed, 163 insertions, 153 deletions
diff --git a/doc/internals.tex b/doc/internals.tex
new file mode 100644
index 000000000..c34b9ec8e
--- /dev/null
+++ b/doc/internals.tex
@@ -0,0 +1,163 @@
+\documentclass{article}
+
+\setlength{\textwidth}{6.75in} % 1 inch side margins
+\setlength{\textheight}{9in} % ~1 inch top and bottom margins
+
+\setlength{\headheight}{0in}
+\setlength{\topmargin}{0in}
+\setlength{\headsep}{0in}
+
+\setlength{\oddsidemargin}{0in}
+\setlength{\evensidemargin}{0in}
+
+\title{Botan Internals}
+\author{Jack Lloyd ([email protected])}
+\date{August 20, 2006}
+
+\newcommand{\filename}[1]{\texttt{#1}}
+\newcommand{\manpage}[2]{\texttt{#1}(#2)}
+
+\newcommand{\function}[1]{\textbf{#1}}
+\newcommand{\type}[1]{\texttt{#1}}
+\renewcommand{\arg}[1]{\textsl{#1}}
+
+\begin{document}
+
+\maketitle
+
+\tableofcontents
+
+\parskip=5pt
+
+\section{Introduction}
+
+This document is intended to document some of the trickier and/or more
+complicated parts of Botan. This is not going to be terribly useful if
+you just want to use the library, but for people wishing to understand
+how it works, or contribute new code to it, it will hopefully prove
+helpful.
+
+I've realized that a lot of things Botan does internally are pretty
+hard to understand, and that a lot of things are only inside my head,
+which is a bad place for them to be (things tend to get lost in there,
+not to mention the possibility that I'll get hit by a truck next
+week).
+
+This document is currently very incomplete. I'll be working on it as I
+have time.
+
+\pagebreak
+
+\section{Filter}
+
+Filter is one of the core abstractions of the library. It represents
+
+\section{Pipe}
+
+Pipe is, conceptually, a tree structure of Filter objects. There is a
+single unique top, and an arbitrary number of leaves (which are
+SecureQueue objects). SecureQueue is a simple Filter that buffers its
+input.
+
+Writing into the pipe writes into the top of the tree. The filter at
+the top of the tree writes its output into the next Filter, and so on
+until eventually data trickles down into the bottommost Filters, where
+the data is stored for later retrieval.
+
+When a new message is started, Pipe searches through the tree of
+Filters and finds places where the \arg{next} field of the Filter is
+NULL. This implies that it was the lowest layer of the Filter tree
+that the user added. It then adds SecureQueue objects onto these
+Filters. These queues are also stored in a \type{std::vector} called
+\arg{messages}. This is how the Pipe knows how to read from them later
+without doing a tree traversal every time.
+
+Pipe will, if asked, destroy the existing tree structure, in order to
+create a new one. However, the queue objects are not deleted, because
+Pipe might need to read from them later.
+
+An optimization in future versions will involve deleting empty queues
+that we ``know'' can't be written to, and then replace their field in
+\arg{messages} with NULL. On reading, Pipe will know that this means
+that the queue is empty, and act as if such a queue was really
+there. This is relatively minor, because in recent versions an empty
+queue only takes up a few dozen bytes (previous to 0.8.4 or so, an
+empty queue still took up 4 kilobytes of memory).
+
+\section{Library Initialization}
+
+A lot of messy corner cases.
+
+\section{Lookup Mechanism}
+
+Most objects know their name, and they know how to create a new copy
+of themselves. We build mapping tables that map from an algorithm name
+into a single instance of that algorithm. The tables themselves can be
+found in \filename{src/lookup.cpp}.
+
+There are a set of functions named \function{add\_algorithm} that can
+be used to populate the tables. We get something out of the table with
+\function{retrieve\_x}, where x is the name of a type
+(\texttt{block\_cipher}, \texttt{hash}, etc). This returns a const
+pointer to the single unique instance of the algorithm that the lookup
+tables know about. If it doesn't know about it, it falls back on
+calling a function called \function{try\_to\_get\_x}. These functions
+live in \filename{src/algolist.cpp}. They are mostly used to handle
+algorithms which need (or at least can have) arguments passed to them,
+like \type{HMAC} and \type{SAFER\_SK}. It will return NULL if it can't
+find the algorithm at all.
+
+When it's asked for an algorithm it doesn't know about (ie, isn't in
+the mapping tables), the retrieval functions will ask the try-to-get
+functions if \emph{they} know about it. If they do, then the object
+returned will be stored into the table for later retrieval.
+
+The functions \function{get\_x} call the retrieval functions. If we
+get back NULL, an exception is thrown. Otherwise it will call the
+\function{clone} method to get a new copy of the algorithm, which it
+returns.
+
+The various functions like \function{output\_length\_of} call the
+retrieval function for each type of object that the parameter in
+question (in this case, \texttt{OUTPUT\_LENGTH}) might be meaningful
+for. If it manages to get back an object, it will return (in this
+case) the \texttt{OUTPUT\_LENGTH} field of the object. No allocations
+are required to call this function: all of its operations work
+directly on the copies living in the lookup tables.
+
+\section{Allocators}
+
+A big (slow) mess.
+
+\section{BigInt}
+
+Read ``Handbook of Applied Cryptography''.
+
+\section{PEM/BER Identification}
+
+We have a specific algorithm for figuring out if something is PEM or
+BER. Previous versions (everything before 1.3.0) requried that the
+caller specify which one it was, and they had to be right. Now we use
+a hueristic (aka, an algorithm that sometimes doesn't work right) to
+figure it out. If the first character is not 0x30 (equal to ASCII
+'0'), then it can't possibly be BER (because everything we care about
+is enclosed in an ASN.1 SEQUENCE, which for BER/DER is encoded as
+beginning with 0x30). Roughly 99.9% of PEM blocks \emph{won't} have a
+random 0 character in front of them, so we are mostly safe (unless
+someone does it on purpose, in which case, please hit them for me).
+But to be sure, if there is a 0, then we search the first \emph{N}
+bytes of the block for the string ``-----BEGIN ``, which marks the
+typical start of a PEM block. The specific \emph{N} depends on the
+variable ``base/pem\_search'', which defaults to 4 kilobytes.
+
+So, you can actually fool it either way: that a PEM file is really
+BER, or that a BER file is actually PEM. To fool it that a BER file is
+PEM, just have the string ``-----BEGIN `` somewhere (I can't imagine
+this string shows up in certificates or CRLs too often, so if it is
+there it means somebody is being a jerk). If a file starts with 0 and
+has at least ``base/pem\_search'' byte more junk in the way, it won't
+notice that its PEM at all. In either case, of course, the loading
+will fail, and you'll get a nice exception saying that the decoding
+failed.
+
+\end{document}
diff --git a/doc/misc/internals.tex b/doc/misc/internals.tex
deleted file mode 100644
index 81eca146a..000000000
--- a/doc/misc/internals.tex
+++ /dev/null
@@ -1,153 +0,0 @@
-\documentclass{article}
-
-\setlength{\textwidth}{6.75in} % 1 inch side margins
-\setlength{\textheight}{9in} % ~1 inch top and bottom margins
-
-\setlength{\headheight}{0in}
-\setlength{\topmargin}{0in}
-\setlength{\headsep}{0in}
-
-\setlength{\oddsidemargin}{0in}
-\setlength{\evensidemargin}{0in}
-
-\title{Botan Internals}
-\author{Jack Lloyd ([email protected])}
-\date{July 30, 2002}
-
-\newcommand{\filename}[1]{\texttt{#1}}
-\newcommand{\manpage}[2]{\texttt{#1}(#2)}
-
-\newcommand{\function}[1]{\textbf{#1}}
-\newcommand{\type}[1]{\texttt{#1}}
-\renewcommand{\arg}[1]{\textsl{#1}}
-
-\begin{document}
-
-\maketitle
-
-\tableofcontents
-
-\parskip=5pt
-
-\section{Introduction}
-
-This document is intended to document some of the trickier and/or more
-complicated parts of Botan. This is not going to be terribly useful if you
-just want to use the library, but for people wishing to understand how it
-works, or contribute new code to it, it will hopefully prove helpful.
-
-I've realized that a lot of things Botan does internally are pretty hard to
-understand, and that a lot of things are only inside my head, which is a bad
-place for them to be (things tend to get lost in there, not to mention the
-possibility that I'll get hit by a truck next week).
-
-This document is currently very incomplete. I'll be working on it as I have
-time.
-
-\pagebreak
-
-\section{Filter}
-
-Need something here.
-
-\section{Pipe}
-
-Pipe is, conceptually, a tree structure of Filter objects. There is a single
-unique top, and an arbitrary number of leaves (which are SecureQueue objects).
-SecureQueue is a simple Filter that buffers it's input.
-
-Writing into the pipe writes into the top of the tree. The filter at the top
-of the tree writes it's output into the next Filter, and so on until eventually
-data trickles down into the bottommost Filters, where the data is stored for
-later retrieval.
-
-When a new message is started, Pipe searches through the tree of Filters and
-finds places where the \arg{next} field of the Filter is NULL. This implies
-that it was the lowest layer of the Filter tree that the user added. It then
-adds SecureQueue objects onto these Filters. These queues are also stored in a
-\type{std::vector} called \arg{messages}. This is how the Pipe knows how to
-read from them later without doing a tree traversal every time.
-
-Pipe will, if asked, destroy the existing tree structure, in order to create a
-new one. However, the queue objects are not deleted, because Pipe might need to
-read from them later.
-
-An optimization in future versions will involve deleting empty queues that we
-``know'' can't be written to, and then replace their field in \arg{messages}
-with NULL. On reading, Pipe will know that this means that the queue is empty,
-and act as if such a queue was really there. This is relatively minor, because
-in recent versions an empty queue only takes up a few dozen bytes (previous to
-0.8.4 or so, an empty queue still took up 4 kilobytes of memory).
-
-\section{Library Initialization}
-
-A lot of messy corner cases.
-
-\section{Lookup Mechanism}
-
-Most objects know their name, and they know how to create a new copy of
-themselves. We build mapping tables that map from an algorithm name into a
-single instance of that algorithm. The tables themselves can be found in
-\filename{src/lookup.cpp}.
-
-There are a set of functions named \function{add\_algorithm} that can be used
-to populate the tables. We get something out of the table with
-\function{retrieve\_x}, where x is the name of a type (\texttt{block\_cipher},
-\texttt{hash}, etc). This returns a const pointer to the single unique instance
-of the algorithm that the lookup tables know about. If it doesn't know about
-it, it falls back on calling a function called
-\function{try\_to\_get\_x}. These functions live in
-\filename{src/algolist.cpp}. They are mostly used to handle algorithms which
-need (or at least can have) arguments passed to them, like \type{HMAC} and
-\type{SAFER\_SK}. It will return NULL if it can't find the algorithm at all.
-
-When it's asked for an algorithm it doesn't know about (ie, isn't in the
-mapping tables), the retrieval functions will ask the try-to-get functions if
-\emph{they} know about it. If they do, then the object returned will be stored
-into the table for later retrieval.
-
-The functions \function{get\_x} call the retrieval functions. If we get back
-NULL, an exception is thrown. Otherwise it will call the \function{clone}
-method to get a new copy of the algorithm, which it returns.
-
-The various functions like \function{output\_length\_of} call the retrieval
-function for each type of object that the parameter in question (in this case,
-\texttt{OUTPUT\_LENGTH}) might be meaningful for. If it manages to get back an
-object, it will return (in this case) the \texttt{OUTPUT\_LENGTH} field of the
-object. No allocations are required to call this function: all of it's
-operations work directly on the copies living in the lookup tables.
-
-\section{Allocators}
-
-A big (slow) mess.
-
-\section{BigInt}
-
-Read ``Handbook of Applied Cryptography''.
-
-\section{PEM/BER Identification}
-
-We have a specific algorithm for figuring out if something is PEM or
-BER. Previous versions (everything before 1.3.0) requried that the caller
-specify which one it was, and they had to be right. Now we use a hueristic
-(aka, an algorithm that sometimes doesn't work right) to figure it out. If the
-first character is not 0x30 (equal to ASCII '0'), then it can't possibly be BER
-(because everything we care about is enclosed in an ASN.1 SEQUENCE, which for
-BER/DER is encoded as beginning with 0x30). Roughly 99.9% of PEM blocks
-\emph{won't} have a random 0 character in front of them, so we are mostly safe
-(unless someone does it on purpose, in which case, please hit them for me).
-But to be sure, if there is a 0, then we search the first \emph{N} bytes of the
-block for the string ``-----BEGIN ``, which marks the typical start of a PEM
-block. The specific \emph{N} depends on the variable ``base/pem\_search'',
-which defaults to 4 kilobytes.
-
-So, you can actually fool it either way: that a PEM file is really BER, or that
-a BER file is actually PEM. To fool it that a BER file is PEM, just have the
-string ``-----BEGIN `` somewhere (I can't imagine this string shows up in
-certificates or CRLs too often, so if it is there it means somebody is being a
-jerk). If a file starts with 0 and has at least ``base/pem\_search'' byte more
-junk in the way, it won't notice that it's PEM at all. In either case, of
-course, the loading will fail, and you'll get a nice exception saying that the
-decoding failed.
-
-\end{document}