Algorithms
If you have Cookies enabled,
you can check to see if any files you have downloaded
have been updated since you downloaded them
by clicking here.
|
|
|
Each of the Algorithms have been implemented as C++ classes using Microsoft Visual C++ V6.
Microsoft Foundation Classes (MFC) have been used where necessary.
Non MFC folk can remove the pragma statements and use the following info to adjust the code:
typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef unsigned long DWORD;
My intention is to provide simple, free access to useable solutions to common but difficult programming problems.
I have treated the creation of each class as a puzzle and hopefully have come up with good solutions.
If you know any better solutions then please e-mail me so that everyone can share your wisdom!
Be aware that I use a non-standard "Coding Style"... and its infectious...
|
itow
Algorithm to convert Numbers to Words
Turns an integer into words.
For example:
itow(1234568790)
gives:
"One Hundred and Twenty Three Million Four Hundred and Fifty Six Thousand Eight Hundred and Ninety"
There are two versions of the class,
one uses the Standard Template Library string class,
the other uses the MFC CString class.
The std::string version is the default.
To use MFC CString Version comment out the line:
#define UseSTLstring
Usage:
std::string Version:
std::string s=Citow::itow(100100);
MFC CString Version:
CString S=Citow::itow(100100);
Word Finder
Algorithm to pick out Words from Text
This class is intended to pick out important sub-strings of data (tokens) from a string.
It was designed for a spell-checker and so currently returns words from sentences.
Its perception of what letters can make up a "word" comes from a table.
This table is currently loaded with characters from dictionaries downloaded from the Internet.
Apostrophe (') is considered part of a word to allow "don't" and "o'clock" etc.
Single letters are ignored.
There are two versions of the class,
one uses the Standard Template Library string class,
the other uses the MFC CString class.
Usage:
std::string Version:
CSTLWordFinder WordFinder("S=WordFinder.GetFirstWord();");
MFC CString Version:
CWordFinder WordFinder("S=WordFinder.GetFirstWord();");
ASSERT( WordFinder.GetFirstWord() =="WordFinder"); // "S" is length 1, therefore, not a "word" but a letter.
ASSERT( WordFinder.GetNextWord() =="GetFirstWord");
ASSERT( WordFinder.GetNextWord() ==""); //(no next word)
ASSERT( WordFinder.GetFirstWord() =="WordFinder");
ASSERT( WordFinder.GetWord() =="WordFinder");
ASSERT( WordFinder.GetWordCapitalised()=="Wordfinder");
ASSERT( *WordFinder =="WordFinder"); //You can use the class as if it were the data
ASSERT( WordFinder++ =="WordFinder"); // "S" is length 1, therefore, not a "word" but a letter.
ASSERT( WordFinder++ =="GetFirstWord");
ASSERT( WordFinder++ ==""); //(no next word)
ASSERT( WordFinder.GetFirstWord() =="WordFinder");
ASSERT( *WordFinder =="WordFinder");
ASSERT(++WordFinder =="GetFirstWord");
ASSERT( *WordFinder =="GetFirstWord");
ASSERT(++WordFinder ==""); //(no next word)
If all you want to do is Capitalise the words in a string (i.e. make the firs letter of each word a Capital Letter (upper case) and the rest lower case) the algorithm is simply this:
void Capitalise(char* ptr) {
--ptr;
bool FirstLetter=true;
while(char c=*++ptr) {
if(isalpha(c) || c=='\'') { // Special case for words like "I'll" which would otherwise become "I'Ll"
if(FirstLetter) {
FirstLetter=false;
*ptr=toupper(c);
}else *ptr=tolower(c);
}else FirstLetter=true;
} }
Heres a version for MFC CString users:
void Capitalise(CString& S) {
char* ptr=S.GetBuffer(0)-1;
bool FirstLetter=true;
while(char c=*++ptr) {
if(isalpha(c) || c=='\'') { // Special case for words like "I'll" which would otherwise become "I'Ll"
if(FirstLetter) {
FirstLetter=false;
*ptr=toupper(c);
}else *ptr=tolower(c);
}else FirstLetter=true;
}
S.ReleaseBuffer();
}
Binary Chop
The Binary Chop Search Algorithm
Binary chop is how a child looks up a friend in a Telephone Directory.
Given that you don't have enough experience of directories to know the likely distribution of names (things like "There are unlikely to be any names starting with letters after 'W'")
the best way to find a name is to open the middle page of the Directory and see what name is at the head of the page.
You can now focus your attention on finding the name in one half of the Directory because the names are in order and you can see if the name you are looking for comes before or after the name in the middle.
So now you ignore half the Directory and repeat the process.
Binary chop means cutting in half each time you look.
It only works for sorted lists but is very fast.
Heres the basic algorithm:
int stt=0;
int mid;
int end=NumberOfListItems;
while(stt!=end) {
mid=(stt+end)/2;
if(List[mid]==target) break;
if(List[mid]> target) end=mid;
else stt=mid+1;
}
bool Found=(List[mid]==target);
|
Checksums
Cyclic Redundancy Check
CRC is a "digital fingerprint" of a file.
Three types of checksum are presented here.
CRC32
With CRC32 you can get a single 32-bit number that represents a string or file (of any size).
If the file data changes in any way (even a single bit) the CRC32 calculation would yield a completely different value.
This algorithm is used by WinZip and PKZIP (ie the same numbers are generated) so:
pkunzip.exe -vt File.zip
gives the same CRC value as you get by giving the file to this code.
A single 1kB table is allocated while instances of CCRC32 exist.
Usage:
int CRC=CCRC32().From(Buffer,Size);
or use one instance for several CRCs:
CCRC32 CRC32;
int CRC1=CRC32.From(Buffer1,Size1);
int CRC2=CRC32.From(Buffer2,Size2);
or if reading a file in blocks:
CCRC32 CRC32;
while(Read(Buffer, Size)) CRC32.From(Buffer, Size, true);
int CRC=CRC32.GetCRC();
}
Working Code for this might be:
int OK;
CCRC32 CRC32;
BYTE Buffer[1024];
FILE* File=fopen("C:\\CheckMe.txt","rb");
if(File) do CRC32.From(Buffer, OK=fread(Buffer, 1, 1024, File), true); while(OK);
fclose(File);
int CRC=CRC32.GetCRC();
But since we want the fastest routines we should use CreateFile
and thats what the class uses internally for retrieving the CRC32 of a file:
int CRC=CCRC32().From("C:\\CheckMe.txt");
Test CRC numbers:
resume = 60C1D0A0
resumé = 84CF1FAB
The file CRC32.h contains code for all of these checksums:
Adler32
Adler32 is another checksum algorithm that is used as a "quick and dirty" version of the CRC32 algorithm (it was invented by Mark Adler).
You get a single 32-bit number that represents a block of data (of any size but >128 bytes preferably).
If the data changes in any way (even a single bit) the Adler32 calculation would yield a completely different value.
It may comfort you to know that this document contains 32 occurances of the word Adler32... or not!
The usage is the same as for CRC32:
int Adler32=CAdler32().From(Buffer,Size);
or use one instance for several Adler32s:
CAdler32 Adler32;
int Adler32a=Adler32.From(Buffer1,Size1);
int Adler32b=Adler32.From(Buffer2,Size2);
or if reading a file in blocks:
CAdler32 Adler32;
while(Read(Buffer, Size)) Adler32.From(Buffer, Size, true);
int MyAdler32=Adler32.GetAdler32();
}
Test Adler32 numbers:
resume = 152371858
resumé = 161022742
The file CRC32.h contains code for all of these checksums:
Fast Checksum
The following algorithm is from a program called rsync which compares blocks of data using a very fast checksum.
If the blocks have the same checksum using this method, they are recompared using a more accurate method (rsync uses MD4) to see if the blocks really are identical.
As with Adler32, it gives better results the larger the block size and 128 Bytes is a good minimum.
Test numbers:
resume = 169870047
resumé = 178520931
RSync has 0 instead of 13 giving the following Checksums:
resume = 151978641
resumé = 160629525
DWORD Checksum(const BYTE* Buffer, DWORD Len) {
for(register DWORD i=0,s1=0,s2=0; i++<Len; s2+=s1+=13+*Buffer++);
return s1+(s2<<16);
}
In most cases its not worth using this as a function - just use the for loop in your code.
The file CRC32.h contains code for all of these checksums:
MD5
Message digest 5
This class generates a 32 byte Hash Code for a given String or File input.
Use this to generate a Unique Identifier or Checksum from a String or for a File.
Short Rand
Short Pseudo-Random Number Generator
A Pseudo Random Number Generator based on Knuth, Vol 2, p. 27.
Returns shorts uniformly distributed over -32768 to 32767
Very short in code as well as type.
The numbers always occur in the same sequence (invariable seed).
#include "ShortRand.h"
main() {
CShortRand SRand;
for(;;) {
short i=++SRand;
WORD d=++SRand;
}
}
If you want a different sequence each time, just Exclusive Or (XOR) the result with (WORD)GetTickCount();
The result will still be many times faster than rand();
short i=++SRand^(WORD)GetTickCount();
Random
Pseudo-Random Number Generator
This class is supposed to be the best Pseudo-Random Number Generator (PRNG).
Its useful where predictable random numbers are required.
(For example a program that wants to present the same data to all users on the same day would be seeded (initialised) using the date).
GetPassword.h uses it.
RC4 Encryption
Fast Encryption
CRC4 implements an algorithm called Arcfour that is believed to be fully interoperable with the RC4 algorithm.
Folk seem to call it Arcfour because RC4 is Trademark of RSA Data Security, Inc.
That might mean that if you're going to use this class for corporate software you should rename it...
I'd rather give credit where its due and use their name for their invention.
The Encrypt and Decrypt methods are only to demonstrate usage and are NOT the correct encryption.
For the full Encryption use my CryptStream class which extends this class using the Rand several times.
Usage:
CString Key;
CString Text;
GetDlgItemText(IDC_Key,Key);
GetDlgItemText(IDC_Text,Text);
CRC4 RC4;
RC4.Encrypt(Key,Text);
SetDlgItemText(IDC_RC4, Data2ASCIIhex(Text));
RC4.Decrypt(Key,Text);
SetDlgItemText(IDC_NewText,Text);
It must be strongly recommended that no two plaintexts are encrypted with the same key.
Otherwise the plaintext can usually be broken, and often even quite easily.
If the two encrypted messages are XORed together, the result is the XOR of the original plaintexts.
Given the encrypted messages are text strings, credit card numbers, or other byte streams with some known properties, the plaintexts can be estimated with great accuracy.
See [DAWSON AND NIELSEN] for more details.
It uses another Pseudo-Random Number Generator (PRNG).
It is designed to produce random bytes to act on data streams.
CryptStream uses it.
You can see a Web page RC4 example here.
RC6 Encryption
Effective Encryption
RC6 is trademark of RSA Data Security, Inc.
They're American, so they're patenting it too.
The difficulty of breaking RC6 is estimated as being min(2^(8*KeyBytes),2^704)
The algorithm can have many variants.
The variant is described as follows:
RC6-/W/R/B
W = Word Size in bits (Default is 32) I made a version with a templated base class to handle different values of W, but found no advantages, particularly as there are no official test vectors for the non-32 bit algorithm.
R = Number of Rounds (R=(Depth+2)<<2; Minimum is Depth=0 (R=4), Default is Depth=3 (R=20), my code has maximum Depth=65535 (R=262148) which would use a 2MB State Table.
B = Key Length in Bytes ((0 <= B <= 255) Default is 16)
AES Submission required W=32 and R=20
The constructor handles the parameter ranges by taking integer and creating a valid value from it:
So the number of rounds, R, can be entered as a Depth; The actual value used is R=(Depth+2)<<2; which puts it in the correct range.
The Key will be truncated if it exceeds 255 Bytes to suit the RC6 Standard.
Usage:
CString key("Patently obvious");
CString S("This is the message that will get encrypted.");
CRC6(Key, S); This encrypts S using default RC6 settings. The length of S increases by one Byte (unless S is an empty string) - the first Byte is 0xFF to indicate encrypted data.
...do something with S here
CRC6(Key, S); This decrypts S.
CryptStream
Stream Encryption/Decryption
This is an implementation of an encryption algorithm called XOR256 that uses RC4.
CryptFile uses it.
A string of data can be encrypted or decrypted given a Key and Depth.
The Key is a String which can be short.
Increasing the Depth (an integer) makes the output harder to crack but slower to encode or decode.
Budding spies should be aware that if you save two files with the same Key and Depth then clever folks with time on their hands reckon they might be able to decode the data.
Usage:
CCryptStream Stream;
if(!Stream.SetDepth(12)) return;
if(!Stream.SetKey("This is the Key")) return;
char Text[]="This is the text";
int Len=strlen(Text);
int Len1=Len>>1;
int Len2=Len-Len1;
Stream.Encrypt((BYTE*)Text,Text,Len1);
Stream.Encrypt((BYTE*)Text+Len1,Text+Len1,Len2);
Stream.Reset();
Stream.Decrypt(Text,(BYTE*)Text,Len);
CryptFile
File Encryption/Decryption
This class overrides the MFC class CFile allowing XOR256 Encrypted files to be serialized.
It uses CryptStream.
Usage:
CCryptFile File("gkcT1P8V",8);
if(!File.Open("C:\\t.txt", CFile::modeRead)) return;
CArchive ar(&File, CArchive::load);
ar << CString("Hello World!") << (BYTE)123;
CSV
Read Comma Separated Value (CSV) Files
This is probably the most useful class around!
This class makes reading text data easy, its used in every large project I've done.
This class was designed to read Comma Separated Value (.CSV) files but has been extended to read other similar formats as well.
CSV Files are text files using one line to represent one Record (Record Separators are \r\n characters).
Fields are separated by a particular character (comma , by default).
eg:
one,2,three,four,5.0
If a Field contains a Field Separator character it should be enclosed in Text Separators (Speech Marks " by default).
eg:
one,2,three,"four, or 4",5.0
If a Field contains a Text Separator, that Text Separator should be doubled up, and the Field should be enclosed in Text Separators.
eg:
the fourth field of:
one,2,three,"4'5"" tall",5.0
would be read as:
4'5" tall
Leading and trailing white space characters are removed.
You can specify multiple field separators:
CString S;
CCSV CSV(&S, "1234,432.234;346:787 65", ",;: ");
ASSERT(CSV.GetFieldCount()==5);
The class also handles e-mail recipient lists
where a field may contain a section in Text Separators followed by a section which will never contain Text or Field separators.
eg:
"Smith, John" <JS@Work.com>, "Jones David" <DJ@Work.com>, Me@Home.com
would be read as the following three records:
"Smith, John" <JS@Work.com>
"Jones David" <DJ@Work.com>
Me@Home.com
Note that the white-space characters between the two sections are replaced with a single space character.
Examples:
#include "CSV.h"
CString S;
CCSV MT(&S,"");
ASSERT(MT.GetFieldCount()==0);
ASSERT(!MT.GetNextField());
ASSERT(S=="");
ASSERT(MT.GetFieldAt(0)=="");
ASSERT(MT.FindField("")==-1);
ASSERT(MT.FindField("none")==-1);
CCSV CSV(&S," one,\"two\",\"thr,ee\" ,\"fo\"\"ur\", \"Smith, John\" <JS@Work.com>");
ASSERT(CSV.GetFieldCount()==5);
ASSERT(CSV.FindField("none")==-1);
ASSERT(CSV.GetNextField());
ASSERT(S=="one");
ASSERT(CSV.GetFieldAt(0)=="one");
ASSERT(CSV[0]=="one");
ASSERT(CSV.FindField("one")==0);
ASSERT(CSV.GetFieldCount()==5);
ASSERT(CSV.GetNextField());
ASSERT(S=="two");
ASSERT(CSV.GetFieldAt(1)=="two");
ASSERT(CSV[1]=="two");
ASSERT(CSV.FindField("two")==1);
ASSERT(CSV.GetFieldCount()==5);
ASSERT(CSV.GetNextField());
ASSERT(S=="thr,ee");
ASSERT(CSV.GetFieldAt(2)=="thr,ee");
ASSERT(CSV.FindField("thr,ee")==2);
ASSERT(CSV.GetFieldCount()==5);
ASSERT(CSV.GetNextField());
ASSERT(S=="fo\"ur");
ASSERT(CSV.GetFieldAt(3)=="fo\"ur");
ASSERT(CSV[3]=="fo\"ur");
ASSERT(CSV.FindField("fo\"ur")==3);
ASSERT(CSV.GetFieldCount()==5);
ASSERT(CSV.GetNextField());
ASSERT(S=="\"Smith, John\" <JS@Work.com>");
ASSERT(CSV.GetFieldAt(4)=="\"Smith, John\" <JS@Work.com>");
ASSERT(CSV[4]=="\"Smith, John\" <JS@Work.com>");
ASSERT(CSV.FindField("\"Smith, John\" <JS@Work.com>")==4);
ASSERT(CSV.GetFieldCount()==5);
ASSERT(!CSV.GetNextField());
ASSERT(S=="");
ASSERT(CSV.GetFieldAt(5)=="");
ASSERT(CSV[5]=="");
ASSERT(CSV.GetFieldCount()==5);
To read from a file:
CFile File;
if(!File.Open("Test.csv", CFile::modeRead|CFile::shareDenyNone)) return;
CArchive Ar(&File, CArchive::load);
CString S;
while(Ar.ReadString(S)) { //For all lines of the file
CCSV CSV;
CString Field;
CSV.Set(&Field,S);
while(CSV.GetNextField()) { //for all Fields of the Record
//The current Field is now stored in CString Field
} }
To read command line arguments from GetCommandLine()
(you should really use __argc and __argv[]):
CString S;
CString First ;
CString Second;
CString Third ;
CCSV CSV(&S, GetCommandLine(), ' ');
CSV.GetNextField(); // Application Path
if(!CSV.GetNextField()) return true; //No Parameters
CString argv(S);
if(CSV.GetNextField() // First Parameter
&& CSV.GetNextField() // Second Parameter
&& CSV.GetNextField() // Third Parameter
&& !CSV.GetNextField()) {
...
}
To create a folder from a Path:
CString CreateBranch(CString Path) { //returns the path that was successfully created.
CCSV CSV(0, Path, '\\');
if(Path.Left(2)=="\\\\") { // \\ComputerName\Share\Directory format
CSV.GetNextField(); //Skip the first two "empty fields"
CSV.GetNextField();
CSV.GetNextField(); //Win9x needs the ComputerName and Share to be used together, so we have to skip the ComputerName too.
}
while(CSV.GetNextField()
&& (SetCurrentDirectory(CSV.GetDone())
|| CreateDirectory(CSV.GetDone(),0)));
return CSV.GetDone(); //could be return CSV.GetEnd().IsEmpty() if you wanted the function to return a bool...
Unix to Unix
Unix to Unix Encoder/Decoder
Encodes binary files to Unix to Unix (UU) formatted Text
and Decodes Unix to Unix (UU) formatted Text to the original binary file.
Implements UUEncode and UUDecode functionality.
This encoding is used to convert binary files into text files so that they can be sent through e-mail systems.
The encoded data is larger than the original data.
Any one encoded line of text will not exceed 62 characters.
Base64 produces smaller encoded files than Unix to Unix (UU).
Usage:
CUU::Encode("c:\\tJpg.uu","c:\\t.Jpg" );
CUU::Decode("c:\\t1.Jpg" ,"c:\\tJpg.uu");
Quoted Printable
Quoted Printable Encoding/Decoding
Encodes and Decodes Text in Quoted Printable format.
Quoted Printable format is used to send files that are mostly plain text through e-mail systems that only handle plain text.
Any special characters are replaced with an escaped sequence ('=' being the escape character).
The encoded data is slightly larger than the original data.
Any one encoded line of text will not exceed 80 characters.
Usage:
CQuotedPrintable::Encode("C:\\t.qp" ,"C:\\t.txt");
CQuotedPrintable::Decode("C:\\t1.txt","C:\\t.qp" );
Base64
Base 64 Encoding/Decoding
Encodes binary files to Base64 formatted Text
and Decodes Base64 formatted Text to the original binary file.
This encoding is used to convert binary files into text files so that they can be sent through e-mail systems.
The encoded data is larger than the original data.
Base64 format is part of the MIME protocol.
Any one encoded line of text will not exceed 77 characters.
Base64 produces smaller encoded files than Unix to Unix (UU).
Usage:
CBase64::Encode("C:\\T.b64" ,"C:\\T.bmp");
CBase64::Decode("C:\\TB64.bmp","C:\\T.b64");
Base32
Base 32 Encoding/Decoding
When turning Binary Data into Text, the shortest text is generated using Base64 encoding.
Usually the conversion takes place because the data is being sent through some medium (like the Internet) which filters or alters some binary values.
Base32 encoded data results in text which is case insensitive. My implementation only uses the capital letters and the digits 4-9.
This means that the most significant bit of each ASCII text Byte is always zero, so the Text can be transmitted through media which only transfer 7-bit data.
It is also useful for human readable codes where someone has to type a license number in because the case doesn't matter, and ambiguous shapes can be resolved:
There is no number zero, so if the user typed a zero they were actually reading the letter Oh: O.
There is no number one, so if the user typed a one they were actually reading the letter Eye: I.
There is no number two, so if the user typed a two they were actually reading the letter Zed: Z.
So when the user has typed the string you can get the Binary Data with:
DWORD CMyDlg::GetData() {
CString S;
GetDlgItemText(IDC_EDIT1, S);
S.MakeUpper();
S.Replace('0','O');
S.Replace('1','I');
S.Replace('2','Z');
DWORD Data=Base32toDWORD(S);
}
static CString DWORDtoBase32(DWORD num) { // DWORD to Base32 Text String conversion:
CString Result;
char* ptr=Result.GetBufferSetLength(7);
for(int shift=0; shift<7*5; shift+=5) {
char c=(char)((num>>shift) & 31);
*ptr++=c+(c<6 ? '4' : 'A'-6);
}
Result.ReleaseBuffer(7);
return Result;
}
static DWORD Base32toDWORD(const char* ptr) { // Base32 Text String to DWORD conversion:
DWORD Result=0;
for(int shift=0; shift<7*5; shift+=5) {
char c=*ptr++;
if(!isBase32(c)) return 0;
Result |= ((c<'A') ? (c-'4') : (6+(c-'A')))<<shift;
}
return Result;
}
static bool isBase32(char c) {return !((c<'4') || ((c>'9') && (c<'A')) || (c>'Z'));}
The line in Base32toDWORD: char c=*ptr++;
could be char c=*ptr++ & 0x3F;
which would mean that you wouldn't need the MakeUpper() earlier.
I haven't done that because it may be important to know if the call to Base32toDWORD failed.
Of course, if its very important to know if the data was not pure Base32, then the Base32toDWORD call should have different parameters and return false if non-Base32 characters are encountered:
bool Base32toDWORD(const char* ptr, DWORD& Result) {...}
Binary to ASCII Hex Text
Here are a couple of helper functions that will convert a CString of binary data to Hex and back.
CStrings hold the length of the string, so the string can hold zero Bytes without being truncated.
The Hex string will be twice as long as the original data.
CString ASCIIhex2Data(const CString& S) { // A helper function for ASCII Hex to Data
CString Data;
int Len=S.GetLength()/2;
const char* src=S;
char* dst=Data.GetBufferSetLength(Len);
for(int i=0; i<Len; ++i) {
BYTE hi=*src++;
hi-=(hi<'A' ? '0' : 'A'-10);
BYTE lo=*src++;
lo-=(lo<'A' ? '0' : 'A'-10);
*dst++=(hi<<4) | (lo & 0x0F); // " & 0x0F" deals with lower-case characters
}
Data.ReleaseBuffer(Len);
return Data;
}
CString Data2ASCIIhex(const CString& S) { // A helper function for Data to ASCII Hex
if(S.IsEmpty()) return "";
CString Text;
int Len=S.GetLength()*2;
const char* src=S;
char* dst=Text.GetBufferSetLength(Len);
for(int i=S.GetLength(); i--;) {
BYTE lo=*src++;
BYTE hi=lo>>4;
lo&=0x0F;
*dst++=hi+(hi>9 ? 'A'-10 : '0');
*dst++=lo+(lo>9 ? 'A'-10 : '0');
}
Text.ReleaseBuffer(Len);
return Text;
}
LZW Compression
Store LZW Compressed data
This is a small suite of simple compression classes that use the LZW algorithm optionally using the GIF coding format.
Unisys patented the LZW algorithm, but the patent has now expired and you are free to use this code without license.
They were designed to store short text messages efficiently.
You can specify a File or a CString or an area of memory for each class to act upon.
The Encoder can be told to create GIF codes in the Stream.
The Decoder automatically decodes GIF or normal LZW.
The code has the following behaviour:
- The Encoder checks to see if Encoding really did compress the data.
- If the data wan't compressed the Encoder output is just a copy of the input.
- If the data was compressed the Encoder output starts with a 0xFF Byte.
- Following the 0xFF Byte is a DWORD containing the Uncompressed data length. Use this to create the buffer for your Decompression.
- The Decoder looks for a leading byte of 0xFF and if it doesn't find one, just copies input to output.
- So if the original data has 0xFF as the first byte and doesn't get smaller after LZW then the Decoder will fail.
- For all other cases you can happily Encode data and know you'll never end up with larger data.
- If you used the default constructor, the function you called to Compress or Decompress will return an error message if anything went wrong.
The simplest way to use a CString to hold the data.
Heres example code for some of the constructors:
CString S("anna and nanna banned bananas and bandannas");
S+=S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S+S;
int Length=S.GetLength();
CLZWEncoder E(S);
// S is now the compressed data (or the original data if no compression was possible).
DWORD CompressedLength=S.GetLength(); // At this point: note the leading 0xFF Byte. S may contain NULLs before its end. GetLength returns the correct length for the compressed data.
if((BYTE)*S==0xFF) {
DWORD UnCompressedLength=*((DWORD*)(&*S+1)); //You can access the UnCompressed data Length from the compressed code
}
CLZWDecoder D(S);
//S is now back to the original data or empty if we ran out of memory or the data was corrupt.
if(S.IsEmpty() && CompressedLength) AfxMessageBox("LZW Decompression Failed");
if(Length!=S.GetLength()) AfxMessageBox("LZW Decompression lost Byte(s)");
A file is specified simply by its Path, a section of memory by its Base and Length.
CLZWEncoder Encoder1;
const char* src="anna and nanna banned bananas and bandannas";
DWORD UnCompressedLength=strlen(src)+1; // +1 to include the NULL terminator.
char* LZW=new char[UnCompressedLength];
S=Encoder1.Encode(src, UnCompressedLength, LZW, UnCompressedLength);
if(!S.IsEmpty()) AfxMessageBox(S);
else{
CompressedLength=Encoder1.GetOutSize();
double Ratio=UnCompressedLength+1./CompressedLength;
CLZWDecoder Decoder1;
char* dst=LZW; //start assuming no compression happened, so destination is the same as the source.
if((BYTE)*LZW==0xFF) { // Decoding is necessary
ASSERT(UnCompressedLength==*((DWORD*)(LZW+1))); //You can access the UnCompressed data Length from the compressed code
dst=new char[UnCompressedLength];
Decoder1.Decode(LZW, CompressedLength, dst, UnCompressedLength);
ASSERT(strcmp(src,dst)==0);
delete dst;
} }
delete LZW;
DeleteFile("ReadMeNow.txt");
CLZWEncoder Encoder2;
Encoder2.Encode("ReadMe.txt", "ReadMe.lzw"); // You could use a memory buffer instead of the .lzw file
CLZWDecoder Decoder2;
Decoder2.Decode("ReadMe.lzw", "ReadMeNow.txt");
The bulk of the code handles the input/output, the compression and decompression are short sections of code.
If you remove the GIF decoding block, the Decoder involves very little code: it should be very clear and easy to alter.
HSL Colour Space
Convert to and from HSL
Colour Space convertion is such a simple thing to want to do and yet is presented inacurately or incompletely everywhere.
So, I'm listing what I believe to be the best code I can that converts between RGB colours and HSL (Sometimes called HLS).
Colours are specified on computers in terms of the intensity of each of the electron guns in the monitor.
There are three guns, one Red, one Green and one Blue (ultimately this means there are just different coloured dots which is what you get on an LCD screen).
The human eye can only perceive 256 levels of intensity, so a Byte is sufficient to store the intensity value.
Unfortunately, when you want to describe a colour its not very easy to do accurately using RGB.
The HSL Colour Space is supposed to be easier.
H is the Hue or colour; S is the Saturation and L is the Lightness (Luminescence).
The ranges are supposed to be:
0-360 for Hue (degrees) - Red being at 0
0-240 for Saturation and Lightness...
H is undefined when S=0;
The Colour Selector in Microsoft Windows, rewrites the standards (anyone surprised?) and uses:
0-239 for Hue
0-240 for Saturation and Lightness...
H is 160 when S=0;
This class reproduces the conversion the Microsoft way.
Heres an MFC project that uses it:
new and delete
Making new and delete safe
This is a short piece regarding creating objects on the stack or the heap and has a little about Operator Overloading.
Imagine you have a class which you want to instantiate using 'new' (create on the heap)...
For example, the following class which encapsulates an integer:
class CMyClass {
int i;
public:
CMyClass(int i) : i(i) {}
virtual ~CMyClass() {}
int Get() const {return i;}
};
You can make a simple additional class that will behave in a similar way to CWaitCursor.
This additional class will call delete for you, from its destructor, when it goes out of scope.
So heres the class:
class CpMyClass {
CMyClass* MyClass;
public:
CpMyClass(int i) {MyClass=new CMyClass(i);}
~CpMyClass() {delete MyClass;}
CMyClass* operator->() {return MyClass;}
};
On construction it constructs a CMyClass object using new, and stores a pointer to it.
The operator->() override allows you to use an instance of this class as a pointer... but the pointer we're returning is the address of the CMyClass object!
So we can write the following two lines, safe in the knowledge that the CMyClass object will be deleted when the CpMyClass object goes out of scope.
CpMyClass pMyClass(4);
int i=pMyClass->GetI();
Of course it would be nice to use:
CMyClass& operator.() {return *MyClass;}
but theres no such thing as operator.()
instead you could use:
CMyClass operator*() const {return *MyClass;}
which would let you write this:
int i=(*MyClass).Get();
or this:
operator CMyClass() const {return *MyClass;}
which would let you write this:
int i=((CMyClass)MyClass).Get();
This seems almost useless - if you're trying to use new and make delete happen when the scope changes you should just be using:
CMyObject MyObject(4);
int i=MyClass.GetI();
...But if you're a Windows Programmer, you'll know that some Windows objects can't be created on the stack frame....
So this was a gentle introduction to Smart Pointers...
Fast Linked List
The Fastest Linked List?
CCList is a sorted Circular linked List with WORD Key.
Algorithmically, this is supposed to be as fast as linked lists get.
The algorithm is the sort of thing used in Assembly Language real time graphics renderers.
Ideally this should be a template class but this is good enough for demonstrating the principle.
The Standard Template Library STL provides list for use as a Linked List, or there is my CSList.h file...
If you want a different key type you have to edit the class and adjust SENTINEL appropriately.
Usage:
CCList CList; // List={SENTINEL};
CList.Add(3); // List={3,SENTINEL};
CList.Add(13); // List={3,13,SENTINEL};
CList.Add(23); // List={3,13,23,SENTINEL};
CList.Add(32); // List={3,13,23,32,SENTINEL};
CList.Add(3); // List={3,3,13,23,32,SENTINEL};
CList.Add(2); // List={2,3,3,13,23,32,SENTINEL};
CList.Delete(13); // List={2,3,3,23,32,SENTINEL};
bool b=CList.Find(23); //b=true;
DWORD Key=CList.GetKey(); //Key=23
b=CList.Next(); //b=true;
Key=CList.GetKey(); //Key=32
b=CList.Next(); //b=false;
CList.Empty(); // List={SENTINEL};
Singly Linked List
Singly Linked List
This implements a fast and neat singly linked list which may be used for insertion sort or data or for Queues etc.
The implementation uses a circular list with a dummy Node (with NULL Data pointer) acting as a Terminator at head and tail.
The classes are template-based to allow any type of Data.
Appending to the list is as fast as Adding to the start of the list.
A Count of Nodes is maintained since the overhead during Insertion or deletion is negligible compared to the memory allocation time.
The Iterator class is normally used to access the data in the List class, though access is available to the First Node which is useful for rotating lists or queues.
Nodes may be quickly moved from one list to another with the Iterator's MoveTo and InsertInto methods.
One list may hold pointers to data held in another list if it calls DropAll before it is deleted (preventing it from deleting the Data is points to when its destructor is called).
The test classes give usage examples.
Note that CSListIterator has only been set up for non-const lists.
If the data class provides a Compare function you can have a sorted list.
class CInteger {
public:
int i;
CInteger(int i) : i(i) {}
int Compare(const CInteger& j) const {return i-j.i;}
};
CSList<CInteger> List;
List.Insert(new CInteger(2));
List.Insert(new CInteger(2)); // Insert allows multiple equal nodes
List.Insert1(new CInteger(3));
List.Insert1(new CInteger(3)); // Insert1 keeps the List with unique nodes
You can add nodes to the beginning or end of the list with Add and Append.
For use as a stack or queue you can access the First nodes data without an iterator.
CSListIterator allows you to iterate a List and access the data at any point (like ForEach).
CSList<CString> List;
List.Add(new CString("Hello "));
List.Add(new CString("world!"));
CString S;
for(CSListIterator<CString> it(List); it; ++it) S+=*it;
ASSERT(S=="Hello World!");
CSListIterator has functions to implement filters such as Move which moves a node to another CSListIterator very quickly.
Balanced Binary Tree
G.M.Adelson-Velskii and E.M.Landis (AVL) Binary Tree
The following code is a simplified and yet optimised AVL Tree which can morph to and from a Doubly-Linked List very quickly and efficiently.
As usual the code is written for readability and maintainability - I wrote a marginally faster version, but it was too ugly to survive.
The normal AVL rebalancing makes lots of status checks which are unnecessary if you just do the rotations at the right time in the code.
The order is determined by your implementation of the Compare function (examples follow):
There must be a function T::Compare(T&) or the function Compare of the Template class CTreeListNode<T> has to be overridden.
In normal use the structure is an AVL Tree (A Binary Search Tree which is optimised (balanced) whenever nodes are Inserted or Deleted).
Once insertion and searching is finished the structure can be turned into a linked list for fast iterations.
The TreeList insertion is faster than linked list insertion for large numbers of nodes (unless the Nodes are inserted in reverse order).
Turning the Tree into a linked list only need happen once all the nodes are inserted.
Then iterating the list is faster than iterating the Tree.
To put some numbers to these ideas:
To insert 32768 nodes in descending order into this structure in List mode took 2 units of time
To insert 32768 nodes in ascending order into this structure in List mode took 3800 units of time
To insert 32768 nodes in ascending order into this structure in Tree mode took 5 units of time
To insert 32768 nodes in descending order into this structure in Tree mode took 6 units of time
There are many ways of implementing AVL Trees and a lot of thought went into choosing the methods used here.
If you think you know a faster or better way then let me know, but I've probably tried it already!
(Examples being:
- Having each node store a pointer to its parent (makes Insert 1/3 faster but makes the code bulky and less readable (and isn't necessary)).
- Using separate code for double rotations (negligible speed increase and creates duplication of code).
- Cut/Link Restructure instead of rotations (big speed decrease (half as long again)).
- Moving methods from one class to another (They're all in the right places:)
)
You can use this Structure just in its Tree mode, or its List mode.
You'd use the Tree to search and sort data quickly or to identify or remove duplicates from data.
It is similar to std::map but (particularly for STL beginners) easier to use (and std::map uses "Red Black" Tree instead of AVL Tree (see http://www.sgi.com/tech/stl/stl_tree.h)).
Any tree is slow to iterate in sorted order in comparison to a Linked List.
An AVL tree is not perfectly balanced.
The height of a perfectly balanced tree is approximately lg n, where n is the number of nodes
whereas the worst case height of an AVL tree is approximately 1.44 lg n.
In practice, however, the AVL height approaches lg n as n gets large and so is almost optimal.
So where n is large and performance counts, AVL trees are preferable to random Binary Trees.
This is a template-based class, requiring the nodes to have a Compare function that returns an int value:
<0, if *this < t
0, if *this == t
>0, if *this > t
For example:
#include <iostream.h>
#include "TreeList.h"
class CInteger {
public:
int i;
CInteger(int i) : i(i) {}
int Compare(const CInteger& j) const {return i-j.i;}
};
main() {
CTreeList<CInteger> TreeList;
TreeList.Insert(new CInteger(1));
TreeList.Insert(new CInteger(2));
TreeList.Insert(new CInteger(2)); //Returns 0 because 2 is already inserted (Duplicates are not stored).
TreeList.Insert(new CInteger(3));
for(CTreeListIterator<CInteger> it(TreeList); it; ++it) cout << it.GetData()->i << endl;
}
Heres an example using the Iterator a little more:
#include "TreeList.h"
#include <fstream.h>
#include <string>
class CMyString {
public:
CMyString(const std::string& S) {String=S;}
int Compare(const CMyString& S) const {return String.compare(S.String);}
std::string String;
};
void SortFile(const char* iPath, const char* oPath) {
ifstream iStream(iPath);
ofstream oStream(oPath);
char Buffer[255];
for(CTreeList<CMyString> Tree; iStream.getline(Buffer, sizeof(Buffer)-1); Tree.Insert(new CMyString(Buffer)));
Tree.Morph2List(); //(This is only worth doing if you're going to iterate more than once)
for(CTreeListIterator<CMyString> it(Tree); it; ++it) oStream << it->String.c_str() << endl; //Note that it-> returns it->GetData() its just easier to write!
it.Last();
while(it) oStream << it--.GetData()->String.c_str() << endl;
}
Heres the same thing using MFC:
#include "TreeList.h"
void SortFile(const char* IPath, const char* OPath) {
CFile IFile,OFile;
if(!IFile.Open(IPath,CFile::modeRead|CFile::shareDenyNone)) return false;
CArchive IAr(&IFile, CArchive::load);
if(!OFile.Open(OPath,CFile::modeCreate|CFile::modeWrite|CFile::shareDenyNone)) return false;
CArchive OAr(&OFile, CArchive::store);
CTreeList<CString> TreeList;
for(CString S; IAr.ReadString(S); TreeList.Insert(new CString(S)));
TreeList.Morph2List(); //(This is only worth doing if you're going to iterate more than once)
for(CTreeListIterator<CString> it(TreeList); it; ++it) OAr.WriteString(*it+"\r\n"); //note that *it returns *(it->GetData()) its just easier to write!
it.Last();
while(it) OAr.WriteString(*(it--.GetData())+"\r\n");
}
If you're new to this sort of thing there are a couple of things you'll need to know:
When using MFC files #include <string> in .cpp files has to be at the top of the file above the static char THIS_FILE[] = __FILE__; section.
Declarations using the Standard Template Library sometimes need a space before the trailing > so this will work:
std::map<std::string, int, std::less<std::string> > UserCode;
and this will give a weird unrelated error (syntax error : missing ',' before identifier 'UserCode') because it sees the >> as the shift-right operator:
std::map<std::string, int, std::less<std::string>> UserCode;
There must be a function T::Compare(T&) or the function Compare of the Template class CTreeListNode<T> has to be overridden.
You must have the word const twice in the Compare function definition!
You can see that the definition must be identical from the Non-MFC example above: std:string has a suitable compare function but the name Comapare is all lower case...
So I had to make a whole new class that just provides a 'Compare' interface to the 'compare' function...
Of course, if you always use the std::string you'd be better off just changing the case of the Compare function in TreeList.h
Heres an example with nodes that contain a CString Key and int data that I used to maintain a count of files with a specific file extension in a given folder.
The CString in each node is the file extension (eg. "cpp") and the int is the count of files with that extension.
This class is going to be used as the node:
class CExtension : public CString {
int Count;
public:
CExtension(CString S) : Count(0) {*((CString*)this)=S;}
int& operator++() {return ++Count;}
};
Ext is a CString currently holding the file extension.
The class has
CTreeList<CExtension> TreeList;
in the header and each time a file is found the following code inserts a new node or increments the count for the files extension:
Ext.MakeLower();
TreeList.Insert(new CExtension(Ext)); // The new CExtension is deleted if a node with this extension already exists.
CTreeListIterator<CExtension> it(Ext);
it.Find(CExtension(S));
int CountOfFilesWithThisExtension=++*it;
Finally a note on my "Behaviour Class"
If you want something to happen to every Node's Data then derive a class from CTreeListNodeBehaviour and use ForAll:
Heres an example class that goes through a Tree of CStrings and puts '<' and '>' characters on either side of the string (so "hello" becomes "<hello>"):
class CTreeListTagger: public CTreeListNodeBehaviour<CString> {
private:
void Behaviour(CString& S) {S='<'+S+'>';}
};
Don't try Deleting or Inserting within Behaviour, the restructuring that they induce will mess up the recursion and Behaviour may be missed on some nodes and done twice on others as a result.
Heres a version that counts the nodes in the Tree...
It is only 25% slower than the GetNodeCount function:
class CTreeListNodeCounter: public CTreeListNodeBehaviour<CString> {
private:
int Count;
void Behaviour(CString&) {++Count;}
public:
CTreeListNodeCounter() : Count(0) {}
int GetCount() const {return Count;}
void Reset() {Count=0;}
};
Its slower because the ForAll function has to pass the Behaviour as a parameter.
If you want some examples of how to use the structure, heres the file I used to test it all with while I was developing it:
and you should look at the following projects in the Freeware section of this site demonstrate the use of DTree.h:
CopyTree
Automatic Picture Namer
File Archiver
BlockFile: malloc for Hard Disks!
CBlockFile was developed to keep many small files in one file, a little like a .tar or .zip file or a database holding many records.
Hard Disks are formatted with fixed Block sizes. One File may occupy many Blocks, but one Block can only hold the data for one File.
I had a Server with 4kB Block size which meant that every file that was just a few Bytes long would take up 4kB of Disk space...
The Server was supposed to be used with a few large files but ended up having thousands of tiny files for a particular application (ESSI files for a CNC Profiler).
I created an application which tokenised and compressed the ESSI files and stored them all in a single BlockFile.
That File currently holds more than 7000 small files and gets Defragmented and backed up at midnight every night.
Its been running now (with Uninterruptible Power Supply) for four years without a problem.
CBlockFile was modeled on the malloc and free routines used in the RAM Memory Allocation routines on all Operating Systems.
Instead of RAM, though, CBlockFile allocates a block in a Disk File (Code is included to make it operate on RAM for debugging).
This implementation uses a struct FileInterface to hold all the file handling routines and uses the standard Low-Level routines defined in io.h
MFC users can change this to use CFile if they prefer.
If any of the boolean routines that aren't called Is...() return false, you must assume that the File is corrupt.
When a Block is Freed, the class will make one large Free Block from adjacent Free Blocks where possible.
If a Freed Block is at the end of the File, the File is shortened.
The Defragment() function will remove all Free blocks from a file.
I Defragment when my Application opens the File:
CopyFile("MyFile.bf", "MyFile.bak", FALSE); //Save File incase of failure
if(!BlockFile.Open("MyFile.bf")) return false;
Say("Defragmenting");
if(!BlockFile.Defragment()) { //If defragmentation fails:
BlockFile.Close();
CopyFile("MyFile.bak", "MyFile.bf", FALSE); //Restore the File
if(!BlockFile.Open("MyFile.bf")) return false;
}
Say("Ready...");
This looks a little paranoid, but when you have many files within one file you have cause to be paranoid!
This code has been thoroughly tested using a "Thrasher" which randomly calls random functions with random parameters...
The code was considered finished when the Thrasher ran through 20,000 calls to its functions without failure.
The following is true for all files, but this is a good place to make sure you know:
It only takes one bit to flip in the File and you could loose all the data it held.
For this reason I recommend that the File is closed as soon as possible to minimise the chance of power failure while the File is open (which is the most likely cause of corruption).
If you leave the File open and your Application hangs or the power fails you may end up with corrupt data.
The following MFC project is to test and prove the reliability of CBlockFile. It uses CThread:
Constants
You may find some of these useful:
If you have useful constants or comments to make the usage of any of these clearer, please e-mail me.
#include <math.h>
#define Infinity 1.7976931348623158e+308 //DBL_MAX from <Float.h> Largest possible double
#define Phi 1.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939 //the Golden Ratio
#define phi -0.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939 //and its inverse
#define PI 3.1415926535897932384626433832795
#define PIby2 1.5707963267948966192313216916398
#define TwoPI 6.283185307179586476925286766559
#define rt2 1.4142135623730950488016887242097 //sqrt(2) This multiplied by the side length of a Square gives the length of the diagonal.
#define rt3 1.7320508075688772935274463415059 //sqrt(3)
#define rt75 0.86602540378443864676372317075294 //sqrt(3/4)
#define Ang5 0.0872664625997164788461845384244 //5° in Radians
#define Ang95 1.6580627893946130980775062300642
#define Ang145 2.5307274153917778865393516143085
#define Ang185 3.2288591161895097173088279217039
#define Ang190 3.3161255787892261961550124601284
#define sin10 0.17364817766693034885171662676931 //=sinl(DtoR(10));
#define sin35 0.57357643635104609610803191282616 //=sinl(DtoR(35));
#define cos35 0.81915204428899178968448838591684 //=cosl(DtoR(35));
#define sin190 -0.17364817766693034885171662676931 //=sinl(DtoR(190));
#define cos190 -0.98480775301220805936674302458952 //=cosl(DtoR(190));
bool Equal (double a, double b) {return fabs(a-b)<1e-6;}
bool LessThan (double a, double b) {return a<b-1e-6;}
bool GreaterThan(double a, double b) {return a>b+1e-6;}
double DtoR(double a) {return (PI*a)/180;}
double RtoD(double a) {return (180*a)/PI;}
double ToCelsius (double F) {return 5.0/9.0*(F-32.0);}
double ToFahrenheit(double C) {return 9.0/5.0* C+32.0 ;}
template <typename T> T min(T a, T b){return a<b ? a : b;}
template <typename T> T max(T a, T b){return a>b ? a : b;}
template <typename T> int sgn(T a) {return a<0 ? -1 : a>0;}
double abs(double a) {return (a<0) ? -a : a;}
long abs(long a) {return (a<0) ? -a : a;}
int NearestOne(double a) {return (int)(a+(a<0 ? -0.5 : 0.5));}
double NearestTen(double a) {return ((int)(a+=5)-((int)a)%10);} //10*(int)(a/10+0.5);}
double Quad(double a, double b) {return hypot(a,b);} // Quadrature: sqrt(a*a+b*b);}
double QuadMi(double a, double b) {return sqrt(a*a-b*b);} // Quadrature Minus
double NormaliseAngle(double a) {a=fmod(a,TwoPI); return a<0 ? a+TwoPI : a;}
double NormaliseSignedAngle(double a) {a=fmod(a,TwoPI); if(a<-PI) return a+TwoPI; if(a>PI) return a-TwoPI; return a;}
void Swap(char& a, char& b) {char tmp=b; b=a; a=tmp;}
void Swap(short& a, short& b) {short tmp=b; b=a; a=tmp;}
void Swap(int& a, int& b) {int tmp=b; b=a; a=tmp;}
void Swap(long& a, long& b) {long tmp=b; b=a; a=tmp;}
void Swap(double& a, double& b) {double tmp=b; b=a; a=tmp;}
int GreatestCommonDivisor(int i, int j) {
while(i!=j)
if(i>j) i-=j;
else j-=i;
return i;
}
//The following are here to show beginners how to do some simple things quickly:
char ToUpper(char c) {return c & ~0x20;}
char ToLower(char c) {return c | 0x20;}
void strcpy(char* dst,const char* src) {while(*dst++=*src++);}
int InStr(const char* ptr, int i, char c) {
for(ptr+=i; *ptr!=c && *ptr++; ++i);
return (*--ptr ? i : -1);
}
struct CWaitCursor {
CWaitCursor() {SetMouseToHourGlass();}
~CWaitCursor() {SetMouseToPointer();}
};
|
Read Multi-line Records
A method to read ahead one line in a File
MIME and SMTP Headers have records that may use more than one line.
So as you read the file a line at a time (in my example, using MFC CArchive::ReadLine - but what you use here doesn't matter) and you get a record that may extend to the next line...
If it does extend to the next line, that line will start with a space or tab character.
Obviously you have to read the line to find out, but if the record didn't get to the next line, there is no "UnReadLine" function...
The solution is to store a line.
You could wrap the code in a class but since my application wasn't using multiple threads or instances of the parent class I use a static CString.
You have to use GetMIMELine for the whole block, but not the whole file, because the 'Store' CString is not used once the end of block (a blank line) is found.
- Makes S become a single string version of the multi-line record (Both lines end up in one string with "\r\n" between them).
- S must be empty to start (this loads both S and Store from the file).
- Returns false when blank line or EOF has been reached.
S.Empty(); //Initialises GetMIMELine.
while(GetMIMELine(S, SMTPAr)) if(!GetMIMEBlock(S, SMTPAr)) break; //Note block header details
So heres the algorithm (touch anything and you'll break it)!
For non-MFC folk, the behaviour of CArchive::ReadString(CString& S) is as follows:
It reads a line from a file.
- The CString reference gets set to the File Line Data without the End-of-Line character(s).
- At End of File it returns FALSE.
- If no data was read before EOF was reached it returns false and the CString is emptied: S="";
bool GetMIMELine(CString& S, CArchive& ar) {
static CString Store;
if(!S.IsEmpty()) S=Store;
else if(!ar.ReadString(S)) return false; //This is a new block, load S and Store.
if(S.IsEmpty()) return false; //Indicate this is the last line.
ar.ReadString(Store); //This must Empty Store if no data is read (CArchive does).
while((*Store==' ') || (*Store=='\t')) {
S+="\r\n"+Store;
ar.ReadString(Store); //This must Empty Store if no data is read (CArchive does).
}
return true;
}
I found life easier if I removed the Tab characters using the following code:
bool GetMIMELine(CString& S, CArchive& ar) {
static CString Store;
if(!S.IsEmpty()) S=Store;
else if(ar.ReadString(S)) S.Replace('\t',' '); //Don't want to have to test for both everywhere.
else return false;
if(S.IsEmpty()) return false; //indicate this is the last line/
ar.ReadString(Store); Store.Replace('\t',' '); //Don't want to have to test for both everywhere.
while(*Store==' ') {
S+=NL+Store;
ar.ReadString(Store); Store.Replace('\t',' '); //Don't want to have to test for both everywhere.
}
return true;
}
Of course using a static CString is not thread-safe or suitable within a class with multiple instances.
This is easily solved by putting the CString Store definition in the class definition in the header file.
Atomic Clock Synchronisation
Use Atomic Clocks!
If your PC is connected to the internet you can use Atomic Clocks to synchronise your PCs clock over the internet for free!
For System Administrators (like me) this can be great on your file servers.
Every 24 hours (if you leave the program running) it will re-synchronise your clock (so make sure you have an internet connection that hangs up automatically) if you pay call charges!
The Windows executable file is available here :
Heres the C++ source code as an MSVC++ Project:
The code for this involves dealing with Locales and Time Zones...
Its written using MFC and Windows Sockets, but you don't need to create a [New][Project][MFC Appwizard(exe)] and opt to include support for Windows Sockets.
The support for Sockets is part of the class and allows you to use the class in a separate Thread.
To use the idea generally I have written a class CAtomic...
The Atomic clocks it attempts to read are from a list of SNTP sites I found on the Internet by searching for "SNTP Site List"
You should do the same and choose sites that are close to you for fastest response time.
It starts at the top of the list and if it can't get a connection and time, it tries the next in the list.
In your Dialog Header file: #include "Atomic.h"
and:CAtomic Atomic;
In your .cpp file: SetWindowText(Atomic.Synch());
Synch can have the parameter Synch(false)
which stops it from changing your system clock.
Password Generator
Create secure but easy to remember Passwords!
People are ever so naughty with passwords... They have things that are easy to remember (and therefore guess) or else they forget them.
I have a system I use for generating passwords that are unguessable, and yet memorable.
An example of a good password is imjE2A13K. It is obviously unguessable, but memorable because it rhymes, the change of case happens after the first rhyming part... But don't use this one - download the generator and get another one!
You can download a Windows executable here:
The MSVC++ Project here:
It uses Random.h.
or the class that creates the passwords here:
If anyone thinks its worth me maintaining or updating any of the above, please e-mail me.