12 Utility Functions and Classes

12.1 The Secure Hash Algorithm

12.2 The Modulus Arithmetic Functions

The modulus arithmetic functions are implemented in the files modarith.h and modarith.cpp. This is not a general library of modulus-based arithmetic. I only implemented what I needed.

unsigned long      mod_add( unsigned long a, unsigned long b, unsigned long mod )

Adds the two numbers a and b in the mod modulus field.

unsigned long      mod_mult( unsigned long a, unsigned long b, unsigned long mod )

Multiplies the two numbers a and b in the mod modulus field.

unsigned long      mod_invert( unsigned long num, unsigned long mod )

Finds the multiplicative inverse of num in the mod modulus field.

mod_result      mod_add_c( unsigned long a, unsigned long b, unsigned long mod )

Adds the two numbers a and b in the mod modulus field returning both the result and the quotient of the modulus operation.

mod_result      mod_mult_c( unsigned long a, unsigned long b, unsigned long mod )

Multiplies the two numbers a and b in the mod modulus field returning both the result and the quotient of the modulus operation.

mod_result      mod_add_c( unsigned long a, unsigned long b )

Adds the two numbers a and b in the 2³² modulus field returning both the result and the quotient of the modulus operation.

mod_result      mod_mult_c( unsigned long a, unsigned long b )

Multiplies the two numbers a and b in the 2³² modulus field returning both the result and the quotient of the modulus operation.

In order to keep these functions from being too slow, I spent a small amount of time profiling and optimizing the C code. I did not convert these routines to assembly language because I wanted the code to remain as portable as possible. The optimizations used should reduce the inefficiencies in the code in a compiler-independent way. Obviously the actual effects of the optimizations depends on the compiler used, but the current code should always be faster than the obvious implementation. The code also has the advantage that it returns the right answer even if it is slower than the more obvious floating point solution.

12.3 The RingBuffer class

The constructors for the RingBuffer class have the following prototype:

explicit      RingBuffer( unsigned size )

Creates a rotating buffer containing size elements.

RingBuffer( const RingBuffer &rhs );

Copy constructor for the RingBuffer class.

The public interface for the RingBuffer class supports writing to and reading from the buffer. In the spirit of the STL, this class also can create an iterator object which allows the programmer to retain multiple entry points into the buffer. The public interface for RingBuffer is shown below.

void      Init();

Initialize the ring buffer's insertion cursor.

unsigned      max_size() const;

Returns the size of the ring buffer.

unsigned      size() const;

Returns the current number of entries in the ring buffer.

unsigned      empty() const;

Returns true if the ring buffer is empty.

void      add( unsigned long val );

Add a new value at the current insertion point.

RingBuffer      &operator=( const RingBuffer &rhs );

Assignment operator for the RingBuff class.

iterator      MakeIterator( unsigned index );

Return an iterator that points to position index in the ring buffer.

iterator      begin();

Return an iterator that points to the beginning of the data in the ring buffer.

iterator      end();

Return an iterator that points after the end of the data in the ring buffer.

void      Print( ostream &os ) const;

Write the current ring buffer to os.

void      Read( istream &is );

Read the current ring buffer from is.

The RingBuffer's iterator has all of the functionality you would expect from an iterator. The iterator's public interface is shown below.

iterator();

Default constructor.

iterator( const iterator &rhs );

Copy constructor.

unsigned      Index() const;

Returns my index into the ring buffer.

const unsigned long      &operator *() const;

Return the value pointed to by this iterator in the ring buffer.

unsigned long      &operator *();

Return the lvalue of the position pointed to by this iterator in the ring buffer.

iterator      operator++();

Preincrement the iterator.

iterator      operator++( int );

Postincrement the iterator.

iterator      operator-{

-();} Predecrement the iterator.

iterator      operator-{

-( int );} Postdecrement the iterator.

iterator      &operator=( const iterator &rhs );

Assign a new iterator to the current iterator.

bool      operator==( const iterator &rhs );

Tests two iterators for equality.

bool      operator!=( const iterator &rhs );

Tests two iterators for inequality.

© 1997 G. Wade Johnson. All rights reserved.
http://www.anomaly.org/ThinAir/utility.html