\documentclass{article}

\usepackage{listings}
\usepackage{a4}
\usepackage{courier}
\usepackage{hyperref}

\lstdefinelanguage{shell} {
  sensitive=true
  }

\lstnewenvironment{ccode}[1][]
  {\lstset{language=c,captionpos=b,frame=single,basicstyle=\scriptsize,float,#1}}
  {} 

\lstnewenvironment{code}[1][]
  {\lstset{language=haskell,captionpos=b,frame=single,basicstyle=\scriptsize,float,#1}}
  {} 

\lstdefinelanguage{ASN1} {
  keywords={CHOICE, SEQUENCE, BEGIN, END, IMPLICIT, EXPLICIT, INTEGER, DEFINITIONS},
  sensitive=false,
  morecomment=[s]{(--}{--)}
  }

\lstnewenvironment{asn1}[1][]
  {\lstset{language=ASN1,captionpos=b,frame=single,basicstyle=\scriptsize,float,#1}}
  {} 

\def\asn#1{{\it #1}}

\setlength{\parskip}{\medskipamount}
\setlength{\parindent}{0pt}

\title{Haskell ASN.1 PER Library 1.0.0}
\author{Dominic Steinitz}

\begin{document}

\maketitle

\section{Introduction}

The 
\htmladdnormallinkfoot
{Haskell ASN.1 PER Library 1.0.0}
{http://www.haskell.org/asn1}
is an implementation of the ASN.1 Packed Encoding Rules (PER).

The current release does not contain a parser for ASN.1 so you have to hand encode
ASN.1 definitions into the Haskell ASN.1 Abstract Syntax Tree (AST). Examples of these are given
for each ASN.1 construction supported.

Haddock documentation for the library is available
\htmladdnormallinkfoot
{here}
{http://www.haskell.org/asn1/doc/html};
alternatively, you can generate it yourself (need to give instructions on how to do this).

The library has been designed to prevent encoding errors at compile time. However, given the nature
of ASN.1 and Haskell, it is not possible to do this in all cases.

The library comes with:

\begin{enumerate}

\item
A pretty printer ({\em Pretty.lhs}) for all supported ASN.1 types.

\item
Tests for each supported type ({\em UnitTest.lhs}).

\item
Properties which are tested
by
\htmladdnormallinkfoot
{QuickCheck}
{http://www.cs.chalmers.se/~rjmh/QuickCheck/}.

\item
Tests for the examples given in
\htmladdnormallinkfoot
{ASN.1 Complete}
{http://www.oss.com/asn1/larmouth.html}
by John Larmouth.

\item
Tests for the examples given in
\htmladdnormallinkfoot
{ASN.1 --- Communication between heterogeneous systems}
{http://asn1.elibel.tm.fr/en/book/index.htm}
by Olivier Dubuisson.

\item
Tests for the examples given in Annex A of
\htmladdnormallinkfoot
{Information technology --- ASN.1 encoding rules: Specification of Packed Encoding Rules (PER)}
{http://www.itu.int/rec/T-REC-X.680-X.693/e}
also known as X.691 (07/2002).

\end{enumerate}

Furthermore, the library also comes with properties tested by QuickCheck of inter-operation with
\htmladdnormallinkfoot
{the open source ASN.1 compiler for C}
{http://lionet.info/asn1c}
(asn1c) subject to asn1c supporting the types supported in the Haskell
library. In other words, arbitrary ASN.1 types and values are generated using QuickCheck,
encoded with asn1c, decoded with the Haskell library and then checked
to ensure that the value decoded in Haskell is the same as the value
encoded in C (and vice versa). 

As well as generating inter-operability tests,
this can also be used to generate ``quick starts'' for C programs using asn1c.

Note that no performance testing has been undertaken and there are no
guarantees about the speed of encoding and decoding.

\section{Inter-Operability Testing}

\subsection{Inter-Operability Testing on Linux}



\subsection{Inter-Operability Testing on Windows}

The inter-operability tests have been performed using
\htmladdnormallinkfoot
{asn1c}
{http://lionet.info/asn1c}
--- an open source ASN.1 compiler for C and
\htmladdnormallinkfoot
{lcc}
{http://www.cs.virginia.edu/~lcc-win32}
--- lcc-win32: a compiler system for windows.
Note that this is free for non-commercial use only.

In order to perform the inter-operability tests yourself, follow the
instructions below.

\begin{itemize}
\item
Install lcc into c:$\backslash$lcc (or whatever directory you prefer).
\item
Add c:$\backslash$lcc$\backslash$bin to the end of your path (Windows Vista):
\begin{itemize}
\item
Go to the Control Panel.
\item
Select \lq System\rq .
\item
Select \lq Advanced system settings\rq .
\item
Click \lq Environment variables \rq .
\item
Find the \lq PATH\rq\ environment variable and choose to edit it.
\item
Add \lq ;c:$\backslash$lcc$\backslash$bin\rq\ to the end of the \lq PATH\rq\ environment variable.
\item
Save and close the windows.
\end{itemize}
\item
Install asnc1 into 
c:$\backslash$users$\backslash$yourname$\backslash$asn1c-0.9.21
(or whatever directory you prefer).
\item
Add c:$\backslash$users$\backslash$yourname$\backslash$asn1c-0.9.21
to the end of your path (Windows Vista):
\begin{itemize}
\item
Go to the Control Panel.
\item
Select \lq System\rq .
\item
Select \lq Advanced system settings\rq .
\item
Click \lq Environment variables \rq .
\item
Find the \lq PATH\rq\ environment variable and choose to edit it.
\item
Add \lq c:$\backslash$users$\backslash$yourname$\backslash$asn1c-0.9.21\rq\
to the end of the \lq PATH\rq\ environment variable.
\item
Save and close the windows.
\end{itemize}
\item
Edit Run.hs and make sure the paths are correctly set. If you have
installed asn1c as above then the paths should be as shown in
Listing~\ref{WindowsSettings}.

\begin{code}[caption={Windows Settings},label=WindowsSettings]

-- Uncomment the line below for Windows
skeletons = "c:\\Users\\Yourname\\asn1c-0.9.21\\skeletons"

-- Comment the line below for Windows
-- skeletons = "/usr/local/share/asn1c"

\end{code}
\item
Now compile or load Run.hs and run it or type main at the command prompt.
This will:

\begin{itemize}
\item
Create a directory.
\item
Generate ASN.1 types and values from the test data.
\item
Compile the ASN.1 with asn1c to generate C stubs.
\item
Generate a main C program.
\item
Compile the C.
\item
Run the C to encode the test values into a file.
\item
Read the test values back from the file and decode them using the Haskell
ASN.1 Library.
\item
Compare the original values with the ones decoded.
\end{itemize}

\end{itemize}

\section{ASN.1 Support}

Note that the types are deduced automatically by the compiler are 
reproduce here to aid understanding.

\subsection{BOOLEAN}

\lstset{language=Haskell}

\begin{lstlisting}[frame=single]
BOOLEAN :: ASNType Bool

falseEncoding = toPer BOOLEAN False
\end{lstlisting}

\subsection{INTEGER}

\begin{lstlisting}[frame=single]
INTEGER :: ASNType Integer
integerEncoding = toPer INTEGER 4096

tInteger5 :: ASNType Integer
tInteger5 = RANGE INTEGER (Just (-1)) Nothing
semiConEncoding = toPer tInteger5  4096
\end{lstlisting}

\subsection{ENUMERATED}

The representation for {\em ENUMERATED} has not been finalised but it is
possible to encode examples such as the ones below (see {\em UnitTest.lhs}).

\begin{lstlisting}[frame=single]
FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
   BEGIN
      Enum1 ::= ENUMERATED {
         red(-6), blue(20), green(-8)
         }
      Enum2 ::= ENUMERATED {
         red, blue, green, ..., yellow, purple
         }
      EnumeratedType1 ::= ENUMERATED {
         a, b(5), c, d(1), ..., e, f(6)
	 }
      enum11 Enum1 ::= red
      enum12 Enum1 ::= blue
      enum13 Enum1 ::= green
      enum21 Enum2 ::= red
      enum22 Enum2 ::= yellow
      enum23 Enum2 ::= purple
   END
\end{lstlisting}

\subsection{REAL}

Not currently supported.

\subsection{BIT STRING}

\begin{lstlisting}[frame=single]
BITSTRING :: NamedBits -> ASNType BitString

encodedBitString = 
   toPer (BITSTRING []) 
         (BitString [1,1,0,0,0,1,0,0,0,0])
\end{lstlisting}

Named bits examples to be provided.

\subsection{CHOICE}

{\bf ASN.1}

\begin{lstlisting}[frame=single]
FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
   BEGIN
      Choice1 ::= 
        CHOICE {
          d INTEGER
	}
      
      Choice2 ::= 
        CHOICE {
	  a INTEGER,
          b INTEGER,
          c INTEGER,
          d INTEGER
        }

      SeqChoices1 ::=
         SEQUENCE {
            x Choice1,
            y Choice2
         }
   END

\end{lstlisting}

{\bf Haskell}

Attempts to encode a {\em CHOICE} with one and only one choice will 
succeed; attempts to encode a {\em CHOICE} with too many or too few
parameters will produce a type error (the ``sizes'' e.g. {\em Z, S Z and S (S Z)} won't match).

\begin{lstlisting}[frame=single]

choice1 = 
   CHOICE xs 
      where
         xs = 
            ChoiceOption 
               (NamedType "a" Nothing INTEGER) NoFChoice

choiceVal1 = ValueC 7 EmptyHL

choice2 = 
   CHOICE xs
      where
         xs = ChoiceOption a (
                 ChoiceOption b (
                    ChoiceOption c (
                       ChoiceOption d NoFChoice
                       )
                    )
                 )
         a = NamedType "a" Nothing INTEGER
         b = NamedType "b" Nothing INTEGER
         c = NamedType "c" Nothing INTEGER
         d = NamedType "d" Nothing INTEGER

choiceVal2 = NoValueC NoValue (
                NoValueC NoValue (
                   NoValueC NoValue (ValueC 7 EmptyHL)
                   )
                )

seqChoices1 = 
   SEQUENCE elems
      where
         elems = Cons x (Cons y Nil)
         x = ETMandatory (NamedType "x" Nothing choice1)
         y = ETMandatory (NamedType "y" Nothing choice2)

\end{lstlisting}

This either needs to be updated or removed.

\begin{lstlisting}[frame=single]

choice1 = 
   CHOICE 
      (ChoiceOption 
          (NamedType "b" Nothing INTEGER) 
          (ChoiceOption (NamedType "a" Nothing BOOLEAN) 
                        NoChoice
          )
      )

tooMany    = 3 :+: (True :+: ASNEmpty)
tooFew     = NoValue :-: (NoValue :-: ASNEmpty)
justRight1 = NoValue :-: (True :+: ASNEmpty)

tooMany :: 
   ASNValue ((:*:) Integer ((:*:) Bool Nil)) (S (S Z))
tooFew :: 
   forall a a1. ASNValue ((:*:) a ((:*:) a1 Nil)) Z
justRight1 :: 
   forall a. ASNValue ((:*:) a ((:*:) Bool Nil)) (S Z)

\end{lstlisting}

\subsubsection{Extensible Type with Addition Groups}

More sophisticated examples such as the one from Annex A.4 in X.691 are
possible. The representation for this has not been finalised but the
current one encodes correctly (see {\em UnitTest.lhs}).

\begin{lstlisting}[frame=single]
FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
   BEGIN
      Ax ::= 
         SEQUENCE {
            a    INTEGER (250..253),
            b    BOOLEAN,
            c    CHOICE {
                    d      INTEGER,
                    ...,
                    [[
                       e BOOLEAN,
                       f IA5String
                    ]],
                    ...
                 },
            ...,
            [[
               g NumericString (SIZE(3)),
               h BOOLEAN OPTIONAL
            ]],
            ...,
            i    BMPString OPTIONAL,
            j    PrintableString OPTIONAL
         }

      axVal Ax ::= 
         {a 253, b TRUE, c e:TRUE, g "123", h TRUE}
   END

\end{lstlisting}

\subsection{SEQUENCE}

\begin{lstlisting}[frame=single]
FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
   BEGIN
      Seq1 ::= 
        SEQUENCE {
          SEQUENCE {
             INTEGER (25..30)
          }
	}
   END
\end{lstlisting}

This {\em SEQUENCE} of a {\em SEQUENCE} consisting of one element
can be represented in the Haskell PER library as follows.

\begin{lstlisting}[frame=single]

tSeq1 = 
   SEQUENCE testSeq1 
      where
         testSeq1  = 
            Cons 
               (ETMandatory 
                  (NamedType "" Nothing (SEQUENCE subSeq1))
                  )
               Nil
         subSeq1  = 
            Cons 
               (ETMandatory 
                  (NamedType "" Nothing consInt1)
                  ) 
               Nil
         consInt1 = 
            RANGE INTEGER (Just 25) (Just 30)

tSeq1 :: ASNType ((:*:) ((:*:) Integer Nil) Nil)

vSeq1 = (27:*:Empty):*:Empty

\end{lstlisting}

\subsection{SEQUENCE OF}

\begin{lstlisting}[frame=single]
FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
   BEGIN
      SeqOfElem1 ::= INTEGER (25..30)
      SeqOf ::=
         SEQUENCE OF SeqOfElem1
   END
\end{lstlisting}

The encoding of a {\em SEQUENCE OF} of 4 elements is shown
below.

\begin{lstlisting}[frame=single]
seqOfElem1 = RANGE INTEGER (Just 25) (Just 30)

test8 = toPer (SEQUENCEOF seqOfElem1) [26,27,28,25]
\end{lstlisting}

\subsubsection{SIZE Constrained SEQUENCE OF}

A {\em SEQUENCE OF} can have restrictions placed on the number
of elements in it. Note that currently there it is possible to
encode a number of elements that lie outside the restricted subset.
In this case, the result is undefined.

{\bf ASN.1}

\begin{lstlisting}[frame=single]
FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
   BEGIN
      SeqOf2 ::=
         SEQUENCE (SIZE (2..5)) OF SeqOfElem1
   END
\end{lstlisting}

{\bf Haskell}

\begin{lstlisting}[frame=single]
seqOft7 = 
   SIZE (SEQUENCEOF seqOfElem1) 
        (Elem (fromList [2..5])) 
        NoMarker

test14 = toPer seqOft7 [26,25,28,27]
\end{lstlisting}

\section{Decoding}

The main decoding function is {\em fromPer}.

\begin{lstlisting}[frame=single]
fromPer :: 
   (
      MonadState (B.ByteString,Int64) m, 
      MonadError [Char] m
   ) 
      =>  ASNType a -> m a
\end{lstlisting}

It necessarily returns a monadic value as errors may occur. Currently it is a state and error monad. 
An alternative version will be supplied
in which {\em m} is the {\em IO} monad as it is envisaged that decoding will occur mostly (but not exclusively)
from externally supplied input.

One possible way of using this decoding function is as follows.

\begin{lstlisting}[frame=single]
import ConstrainedType
import qualified Data.ByteString.Lazy as B
import Control.Monad.State
import Control.Monad.Error
import IO

readPerFile (NamedType _ _ t) =
   do h <- openFile "my.per" ReadMode
      b <- B.hGetContents h
      let d = runState (runErrorT (mFromPer t)) (b,0)
      case d of
         (Left e,s)  -> return (e ++ " " ++ show s)
         (Right n,s) -> return (show n ++ " " ++ show s)
\end{lstlisting}

\section{Installation Instructions}

Get the sources:

\lstset{language=shell,basicstyle=\ttfamily\small}
\begin{lstlisting}[frame=single]
darcs get --tag "1.0.0" http://darcs.haskell.org/asn1
\end{lstlisting}

Build and install ready for testing:

\begin{lstlisting}[frame=single]
ghc -o Setup Setup.hs -package Cabal
./Setup configure --prefix=/my/chosen/dir
./Setup build
./Setup install --user
\end{lstlisting}

Run the tests.

\begin{lstlisting}[frame=single]
cd /my/chosen/dir/bin
./UnitTest
./QuickTest
\end{lstlisting}

If you want to run the inter-operability tests you will need to install asn1c.

\begin{lstlisting}[frame=single]
Instructions for installing asn1c and running the tests.
\end{lstlisting}

You can now run the examples to confirm further that everything
is working satisfactorily.
When you are happy, build and install them in
their final destination:

\begin{lstlisting}[frame=single]
./Setup unregister --user
./Setup clean
./Setup configure
./Setup build
./Setup install
\end{lstlisting}

\subsection{Building the Documentation}

One of the bibliographies is available
courtesy of
\htmladdnormallinkfoot
{Miguel A. Garcia-Martin}
{http://ea1dof.googlepages.com/bibtex}
.
You will need to download it if you want to generate the correct references.

\section{To Do}

In no particular order:

\begin{itemize}

\item
Parser.

\item
Object classes.

\item
Improvement of {\em getBit} performance (the fundamental function in decoding).

\end{itemize}

\section{Text From Pretty}
Some notes:

\begin{enumerate}

\item
ASN.1 is an abstract way of representing data and concrete representations (in terms of bits).
\item
We represent ASN.1 as an Abstract Syntax Tree.
This can either be displayed as the original ASN.1 or it can be displayed as a DTD
(I think this is possible --- that's what asn1c can do).
It's also possible to display it as C code which uses asn1c (http://lionet.info/asn1c).
\end{enumerate}

\subsection{Test Strategy}
\begin{enumerate}
\item
Download and install the asn1c software.
\item
Create some ASN.1 types using the Haskell AST.
\item
Run Pretty.hs to format them as ASN.1.
\item
Run asn1c to generate the C code to handle those ASN.1 types.
\item
Run Asn1cTest.hs to generate a C program which encodes values of the ASN.1 types.
\item
Compile and run the C program. This will encode some values.
\item
Run Test.lhs with the ASN.1 types to decode the values encoded with the C program.
These should be the values you first thought of.
\end{enumerate}


\section{Contact}

All questions, comments, bug reports, flames, requests for 
updates / changes and suggestions should be directed to Dominic Steinitz and
logged
\htmladdnormallinkfoot
{here}
{http://code.google.com/p/hasn1/}
.

The modules in the library come from different authors and have been 
released under different licences. 

\section{Licensing}

This license is based on
\htmladdnormallinkfoot
{The BSD License}
{http://www.opensource.org/licenses/bsd-license.php}.

Redistribution and use in source and binary forms, with or without 
modification, are permitted provided that the following conditions are met:

\begin{itemize}
\item
Redistributions of source code must retain the above copyright notice, 
this list of conditions and the following disclaimer.
\item
Redistributions in binary form must reproduce the above copyright notice, 
this list of conditions and the following disclaimer in the documentation 
and/or other materials provided with the distribution.
\item
The names of its contributors may not be used to endorse or promote 
products derived from this software without specific prior written permission.
\end{itemize}

\begin{sc}
This software is provided by the copyright holders and contributors ``AS IS'' 
and any express or implied warranties, including, but not limited to, 
the implied warranties of merchantability and fitness for a particular 
purpose are disclaimed. In no event shall the copyright owners or
contributors be liable for any direct, indirect, incidental, special,
exemplary, or consequential damages (including, but not limited to,
procurement of substitute goods or services; loss of use, data, or profits;
or business interruption) however caused and on any theory of liability,
whether in contract, strict liability, or tort (including negligence or
otherwise) arising in any way out of the use of this software,
even if advised of the possibility of such damage.
\end{sc}

\section{Contributors}

\begin{itemize}

\item
\htmladdnormallinkfoot
   {Dan Russell}
   {http://www.kingston.ac.uk/~ku02309/}

\item
Dominic Steinitz

\end{itemize}

This document was last updated on 4th November 2007.
\copyright\ 2006--2007 Dominic Steinitz. 

\end{document}
