Common algorithm

xiaoxiao2021-03-06  58

Home Forum News Articles Download Source User Works Cooperation Development Recruitment Tray Service Program Fans CD

Please log in or register new user username password to remember password registration new user forgot password

Your location: Programming Lovers Forum - C / C Language Discussion Area - I have seen some common algorithms

C / C language discussion area: Question Posts The essence of the featured posts No reply Search Subscribe to the collection point here to jump to other discussion Zone Station Discussion Forum Forum Announcement Zone Novice Getting Started Visual Basic Discussion Area C / C Language Discussion Visual C discussion area C Builder discussion area Delphi discussion area Visual FoxPro discussion area PowerBuilder discussion area PASCAL language discussion area QBasic discussion area Java discussion area Game Development Discussion Area assembly language discussion area FORTRAN discussion area WinAPI discussion area Software Creative district programming software download area database development Discussion Forum JBuilder discussion area ASP discussion area PHP discussion area JSP discussion area website production discussion area UNIX & Linux development discussion district programmer Life programmer exam exchange area .NET development discussion area C # discussion area algorithm seminar software engineering and management programming software use area Original Software Test Exchange Area CD Burning Service Area Recruitment Zone Second-hand Books Exchange Area

Pay attention to this post Print this page Save Page This topic Access number: 474

Topic: I've seen some of the commonly used algorithms: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 22:54:12 [Reply]

Landlord

Some things I saw online, post it for your reference. Allowingly, weighing the moon

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 22:55:17 [Reply]

First floor

Sender: Marslv (Dream Life), Letter Area: Program Title: Algorithm - Black and White Qi (Transfer) Send Station: BBS Shantou University Tulip Station (Sat Oct 21 23:57:24 2000), transfer sender: Jek (study hard every day), the letter area: Program Title: Black and white chess pieces: BBS 园 风 站 (SAT Mar 11 14:50:46 2000), transfer // black and white chess #include

INT SP;

Char C [20];

INT I, M;

Void MV (int);

Void Mos (int);

void main ()

{INT N;

COUT << "INPUT (N> = 4)"; cin >> n;

m = n;

For (i = 1; i <= n; i )

{C [i] = '0'; C [i n] = '1';}

SP = N * 2 1;

MV (N);

CIN >> I;

}

Void MV (INT N)

{

IF (n == 4)

{

MOS (4);

MOS (8);

MOS (2);

MOS (7);

MOS (1);

}

Else

{

MOS (N);

MOS (2 * N-1);

MV (N-1);

}

}

Void MOS (INT K)

{

C [sp] = C [k];

C [SP 1] = C [K 1];

sp = K;

C [k] = '_';

C [K 1] = '_';

For (i = 1; i <= 2 * m 2; i )

Cout <

Cout <

}

-

.- ~ /

/ `- '/.'` -:

| / `._ | | .-. {

/ | `- '`.

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 22:56:20 [Reply]

Second floor

Sender: laohong (batch processing), the letter area: Program Title: Calculate 24 points of program sending station: BBS Shantou University Tulip Station (Sun Sep 9 18:30:55 2001), transfer to everyone has been taking Calculation 24, it is better to put a procedure, you can solve any calculation 24 in 1 second. Of course, you want to count 25, 26 ... too. I hope to use this as a 24 problem end. #Include "stdafx .h "// // Principle, 4 numbers and 3 operators press" Polish Expressions "to form a sequence, // calculate whether the value of the sequence is the target. The composition of this sequence can be performed // Traverse to determine if there is a solution. // According to my calculation, if it is limited to the digital calculation between 1-10, there are a total of // 715 different topics, of which 566 have a solution. If it is 1-13, There is // 1820 different questions, 1362 INT TOTAL = 0; // Solutions INT SP; // Current expression stack pointer INT S [7]; // Expression Stack Void Evaluate (int & fz, int & fm) // calculate the value of the expression, Fz, FM is a molecule of the calculation result, splitter {INT OP, L, M, OPN [4]; OP = S [sp]; // Sub-arrow Top element for (l = 0; l <4; l = 2) {IF ((M = S [ sp])> 0) // is digital {OPN [L] = M; OPN [L 1 ] = 1;} else // is the operator EVALUATE (OPN [L], OPN [L 1]);} // calculated according to the operator // OPN [0] / OPN [1] is the first operation Number, // OPN [2] / OPN [3] is the second operand, Switch (OP) {case -4: // Multiplication FZ = OPN [0] * OPN [2]; fm = opn [1] * OPN [3]; Break; case -3: // added FZ = opn [0] * OPN [3] OPN [1] * OPN [2]; fm = opn [1] * OPN [3]; Break Case -2: // subtraction FZ = opn [0] * OPN [3] - OPN [1] * OPN [2]; FM = OPN [1] * OPN [3]; Break; Case-1: // Division FZ = OPN [0] * OPN [3]; fm = opn [1] * OPN [2]; Break;}} void display (cstring & m) // convert express into string {INT I; cstring n; CString n; m = ""; for (i = 0; i <7; i ) {switch (s [i]) {case -4: m = "*"; break; case -3: m = " "; Break; Case -2: m =" - "; Break; Case -1: m =" / "; break; default: n.format ("% 3d ", s [i]); m = N; Break;}}} Void Compute (int Target, Int A, INT B, INT C, INT D, CSTRINGARRAY & MA) // Target - Calculation results (generally 24) // a, b, c, d - The four digits // mA - solution character string expression form {INT L1, L2, L3, OP1, OP2, OP3;

INT L, FZ, FM, NUM [4]; CString M; // Record the arrangement of four elements in the middle of the expression // where LOC [i] [0], LOC [i] [1] represents the second, first The position of three operators // LOC [i] [2], LOC [i] [3] represents the first, second two operands position int LOC [5] [4] = {{1, 2 , 3, 4}, {1, 4, 2, 3}, {2, 3, 1, 4}, {2, 4, 1, 3}}; // Num A, B, C, D arrangement for (L1 = 0; L1 <4; L1 ) {NUM [L1] = A; For (L2 = 0; L2 <4; L2 ) {IF (L2 == L1) Continue; NUM [L2] = B; for (L3 = 0; L3 <4; L3 ) {IF (L3 == L1 || L3 == L2) Continue; Num [L3] = C; Num [6 - L1 - L2 - L3] = D; // Expression Last two must be digital S [5] = Num [2]; s [6] = NUM ​​[3]; for (l = 0; l <5; l ) {S [LOC [L] [2]] = NUM ​​[0]; S [LOC [L] [3]] = NUM ​​[1]; for (OP1 = -4; OP1 <0; OP1 ) {//// Expression first must operate S [0] = op1; for (OP2 = -4; OP2 <0; OP2 ) {S [LOC [L] [0]] = OP2; for (OP3 = -4; OP3 <0; OP3 ) {S [LOC [L] [1]] = OP3; SP = 0; Evaluate (FZ, FM); // Division is not 0, can be divided, the business is 24 indicates the calculation of success IF (FM! = 0 && fz% FM == 0 && fz / fm == target) {Display (m); m.add (m); Total ; // Here, Return is just a solution, / / ​​Otherwise, it is true Solution (no exclusion re-explanation) return;}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 22:57:32 [Reply]

On the 3rd floor

Sender: MARSLV (Dream Life), Letter Area: ProGram Title: Huffman Algorithm (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:42:31 2000), Transmission Sender: Bury (Decades Burial), letter area: Programming Title: Huffman Algorithm Send Station: Yi Xian Tempoken Yat-Sen Channel (Wed Apr 19 13:37:43 2000), Station Letter Send Station: BBS Shuimu Tsinghua Station (SAT Feb 26 23:47:50 2000) I wrote a C program, just in the stations of the Chinese workers, there is VC on the stone, just post it, the algorithm process should be the most important, and many of the digital compression has a Huffman algorithm. . #include

#include

#include

#include

#include

#include

#include

#include

#include

#define EXIT_OK 0

#define exit_failed -1

//

File * infile, * outfile;

Unsigned long int textsize = 0, CODESIZE = 0, PrintCount = 0;

Void error (char * message)

{

Printf ("/ n% s / n", message);

EXIT (-1);

}

/ * Lzss parameters * /

#define N 4096 / * Size of string buffer * /

#define f 60 /// * Size of Look-ahead buffer 60

#define threshold 2

#define nil n / * end of tree's node * /

Unsigned char

Text_buf [n f -1]; // - 1

Int match_position, match_length,

LSON [N 1], RSON [N 257], DAD [N 1];

Void inittree (void) / * Initializing Tree * /

{

INT I;

For (i = n 1; i <= n 256; i )

RSON [I] = nil; / * root * /

For (i = 0; i

DAD [i] = nil; / * node * /

}

Void InsertNode (int R) / * Inserting Node to the Tree * /

{

INT I, P, CMP;

UNSIGNED Char * Key;

Unsigned C;

CMP = 1;

Key = & text_buf [r];

P = N 1 key [0];

RSON [R] = LSON [R] = NIL;

match_length = 0;

For (;;) {

IF (CMP> = 0) {

IF (RSON [P]! = nil)

P = rson [p];

Else {

RSON [P] = R;

DAD [R] = P;

Return;

}

} else {

IF (LSON [P]! = nil)

P = LSON [P];

Else {

LSON [P] = R;

DAD [R] = P;

Return;

}

}

For (i = 1; i

IF ((CMP = Key [I] - text_buf [p i])! = 0)

Break;

IF (i> threshold) {

IF (i> match_length) {

Match_position = ((R - p) & (n - 1)) - 1;

IF ((Match_Length = I)> = f)

Break;

}

IF (i == match_length) {

IF ((C = ((R - P) & (N - 1)) - 1)

Sitoon) {

Match_position = C;

}

}

}

}

DAD [R] = DAD [P];

LSON [R] = LSON [P]; RSON [R] = RSON [P];

DAD [LSON [P]] = R;

DAD [RSON [P]] = R;

IF (RSON [DAD [P]] == P)

RSON [DAD [P]] = R;

Else

LSON [DAD [P]] = R;

DAD [P] = NIL; / * Remove P * /

}

Void deletenode (int P) / * deleding node from the Tree * /

{

INT Q;

IF (DAD [P] == NIL)

Return; / * unregistered * /

IF (RSON [P] == NIL)

Q = LSON [P];

Else

IF (LSON [P] == NIL)

Q = RSON [P];

Else {

Q = LSON [P];

IF (RSON [q]! = nil) {

Do {

Q = rson [q];

} while (rson [q]! = nil);

RSON [Q]] = LSON [q];

DAD [qson [q]] = DAD [q];

LSON [q] = lson [p];

DAD [LSON [P]] = Q;

}

RSON [q] = rson [p];

DAD [RSON [P]] = Q;

}

DAD [q] = DAD [P];

IF (RSON [DAD [P]] == P)

RSON [DAD [P]] = Q;

Else

LSON [DAD [P]] = Q;

DAD [P] = NIL;

}

/ * Huffman Coding Parameters * /

#define n_char (256 - Threshold F)

/ * CHARACTER CODE (= 0..n_Char-1) * /

#define t (n_char * 2 - 1) / * size of table * /

#define r (t - 1) / * root position * /

#define max_freq 0x8000

}

/ * Update When Cumulative Frequency

* /

/ * REACHES to this Value * /

Typedef unsigned char uchar;

/ *

* Tables for Encoding / Decoding Upper 6 Bits of

* SLIDING DICTIONARY POINTER

* /

/ * Encoder Table * /

Uchar p_len [64] = {

0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08};

Uchar p_code [64] = {

0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,

0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9c,

0xA0, 0xA4, 0xA8, 0xAc, 0xB0, 0xB4, 0XB8, 0XBC,

0xc0, 0xc2, 0xc4, 0xc6, 0xc8, 0xca, 0xcc, 0xce,

0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,

0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xea, 0xec, 0xee,

0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,

0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff

}

/ * Decoder Table * /

Uchar d_code [256] = {

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,

0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,

0x0a, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a,

0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b,

0x0c, 0x0c, 0x0c, 0x0c, 0x0d, 0x0d, 0x0d, 0x0d,

0x0e, 0x0e, 0x0e, 0x0e, 0x0f, 0x0f, 0x0f, 0x0f,

0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,

0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,

0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,

0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,

0x18, 0x18, 0x19, 0x19, 0x1a, 0x1a, 0x1b, 0x1b,

0x1c, 0x1c, 0x1d, 0x1d, 0x1e, 0x1e, 0x1f, 0x1f, 0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,

0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,

0x28, 0x28, 0x29, 0x29, 0x2a, 0x2a, 0x2b, 0x2b,

0x2c, 0x2c, 0x2d, 0x2d, 0x2e, 0x2e, 0x2f, 0x2f,

0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,

0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,

}

Uchar d_len [256] = {

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

}

Unsigned freq [t 1]; / * cumulative freq table * /

/ *

* Pointing Parent Nodes.

* Area [T .. (T N_CHAR - 1)] Are Pointers for Leaves

* /

INT PRNT [T N_CHAR];

/ * Pointing Children Nodes (Son [], SON [] 1) * /

Int Son [T];

Unsigned getbuf = 0;

Uchar getlen = 0;

INT getBit / * get one bit * /

{

INT I;

WHILE (getlen <= 8) {

IF ((i = getc (infile)) <0) i = 0;

GetBuf | = i << (8 - getlen);

Getlen = 8;

}

i = GetBuf;

GetBuf << = 1;

Getlen--

Return (i <0);

}

INT getByte (void) / * get a byte * /

{

Long Int i;

WHILE (getlen <= 8) {

IF ((i = getc (infile)) <0) i = 0;

GetBuf | = i << (8 - getlen);

Getlen = 8;

}

i = GetBuf;

GetBuf << = 8;

Getlen - = 8;

Return (I >> 8);

}

Unsigned putbuf = 0;

Uchar PUTLEN = 0;

Void Putcode (int L, unsigned C) / * Output c bits * /

{

Putbuf | = C >> PUTLEN;

IF ((PUTLEN = L)> = 8) {

PUTC (Putbuf >> 8, Outfile);

IF ((PUTLEN - = 8)> = 8) {

PUTC (Putbuf, Outfile);

CODESIZE = 2;

PUTLEN - = 8;

Putbuf = c << (l - poweren);

} else {

Putbuf << = 8;

CODESize ;

}

}

}

/ * Initialize Freq Tree * /

Void startHUFF ()

{

INT I, J;

For (i = 0; i

FREQ [i] = 1;

SON [i] = i t;

PRNT [i T] = i;

}

i = 0; j = n_char;

While (j <= r) {

FREQ [J] = freq [i] freq [i 1]; SON [J] = i;

PRNT [I] = PRNT [i 1] = j;

i = 2; J ;

}

FREQ [T] = 0xffff;

PRNT [R] = 0;

}

/ * Reconstruct Freq Tree * /

Void reconst ()

{

INT I, J, K;

Unsigned f, L;

/ * Halven Cumulative Freq for Leaf Nodes * /

J = 0;

FOR (i = 0; i

IF (SON [i]> = t) {

FREQ [J] = (FREQ [I] 1) / 2;

SON [J] = SON [I];

J ;

}

}

/ * Make a tree: first, connect children nodes * /

For (i = 0, j = n_char; j

K = i 1;

f = freq [j] = freq [i] freq [k];

FOR (k = j - 1; f

K ;

L = (j - k) * 2;

/ * MOVMEM () is Turbo-C Dependent

ReWritten to Memmove () by kenji * /

/ * MOVMEM (& FREQ [K], & FREQ [K 1], L); * /

(void) Memmove (& FREQ [K 1], & FREQ [K], L);

FREQ [k] = f;

/ * MOVMEM (& Son [K], & Son [K 1], L); * /

(void) Memmove (& Son [K 1], & Son [K], L);

SON [K] = i;

}

/ * Connect Parent Nodes * /

FOR (i = 0; i

IF ((k = SON [i])> = t) {

PRNT [K] = I;

} else {

PRNT [K] = PRNT [K 1] = I;

}

}

}

/ * Update Freq Tree * /

Void Update (INT C)

{

INT I, J, K, L;

IF (Freq [R] == Max_FREQ) {

Reconst ();

}

C = prNT [C T];

Do {

K = freq [c];

/ * Swap nodes to keep the tree freq-order * /

IF (k> freq [l = c 1]) {

While (K> FREQ [ L]);

L -;

FREQ [C] = FREQ [L];

FREQ [L] = K;

i = SON [C];

PRNT [I] = L;

IF (i

J = SON [L];

SON [L] = i;

PRNT [J] = C;

IF (j

SON [C] = J;

C = L;

}

} while ((c = prNt [c])! = 0); / * do it until Reaching the root * /

}

UNSIGNED CODE, LEN;

Void EncodeChar (unsigned C)

{

UNSIGNED I;

INT J, K;

i = 0;

J = 0;

K = prNT [C T];

/ * Search Connections from Leaf Node to the root * /

Do {

I >> = 1;

/ *

IF Node's Address Is Odd, Output 1

Else Output 0

* /

IF (k & 1) i = 0x8000;

J ;

} while ((k = prNt [k])! = r);

Putcode (j, i);

Code = i;

LEN = J;

Update (c);

}

Void EncodePosition (unsigned C)

{

UNSIGNED I;

/ * OUTPUT UPPER 6 BITS with encoding * /

I = C >> 6;

Putcode (p_len [i], (unsigned) p_code [i] << 8);

/ * OUTPUT LOWER 6 BITS DIRECTLY * /

Putcode (6, (C & 0x3F) << 10);

}

void encodend ()

{

IF (Putlen) {

PUTC (Putbuf >> 8, Outfile);

CODESize ;

}

}

Int decodechar ()

{

Unsigned C;

C = SON [R];

/ *

* Start Searching Tree from the root to leaves.

* choose node # (SON []) if INPUT bit == 0

* Else Choose # (SON [] 1) (Input bit == 1)

* /

While (c

C = getBit ();

C = SON [C];

}

C - = T;

Update (c);

Return C;

}

Int decodePosition ()

{

Unsigned I, J, C;

/ * Decode Upper 6 Bits from Given Table * /

i = getByte ();

C = (unsigned) D_CODE [i] << 6;

J = D_LEN [I];

/ * Input Lower 6 bits Directly * /

J - = 2;

While (j--) {

i = (i << 1) getBit ();

}

RETURN C | I & 0x3F;

}

/ * Compression * /

Void Encode (void) / * encoding / compressing * /

{

INT I, C, LEN, R, S, LAST_MATCH_LENGTH;

FSeek (Infile, 0L, 2);

Textsize = ftell (Infile);

IF (& TextSize, Sizeof Textsize, 1, Outfile <1)

Error ("Unable to write"); / * Write size of Original Text /

IF (TextSize == 0)

Return;

Rewind (Infile);

Textsize = 0; / * Rewind and rescan * /

STARTHUFF ();

INITTREE ();

S = 0;

R = N - f;

For (i = S; i

TEXT_BUF [I] = '';

For (len = 0; len

TEXT_BUF [R LEN] = C;

Textsize = len;

For (i = 1; i <= f; i )

INSERTNODE (R - I);

INSERTNODE (R);

Do {

IF (Match_length> LEN)

Match_gength = len;

IF (Match_Length <= threshold) {

match_length = 1;

Encodechar (Text_buf [R]);

} else {

EncodeChar (255 - Threshold Match_length);

EncodePosition; Match_Position;

}

Last_match_length = match_length;

For (i = 0; i

(c = getc (infile))! = EOF; i ) {

DELETENODE (S);

TEXT_BUF [S] = C;

IF (S

TEXT_BUF [S N] = C;

S = (S 1) & (n - 1);

R = (R 1) & (n - 1);

INSERTNODE (R);

}

IF ((TextSize = I)> PrintCount) {

Printf ("% 12LD / R", TextSize);

PRINTCOUNT = 1024;

}

While (i

DELETENODE (S);

S = (S 1) & (n - 1);

R = (R 1) & (n - 1);

IF (--LEN) INSERTNODE (R);

}

WHILE (LEN> 0);

Encodend ();

Printf ("INPUT:% LD BYTES / N", TextSize);

Printf ("OUTPUT:% LD BYTES / N", CODESize;

}

Void Decode (int pnum, int all) / * decoding / uncompressing * /

{

INT I, J, K, R, C;

Unsigned long int count;

IF (& Textsize, Sizeof Textsize, 1, Infile <1)

Error ("Unable to read"); / * read size of Original Text * / if (TextSize == 0)

Return;

STARTHUFF ();

For (i = 0; i

TEXT_BUF [I] = '';

R = N - f;

For (count = 0; count

C = decodeChar ();

IF (c <256) {

PUTC (C, OUTFILE);

Text_buf [R ] = C;

R & = (n - 1);

COUNT ;

} else {

I = (r - decodePosition () - 1) & (n - 1);

J = C - 255 Threshold;

For (k = 0; k

C = TEXT_BUF [(i K) & (n - 1)];

PUTC (C, OUTFILE);

Text_buf [R ] = C;

R & = (n - 1);

COUNT ;

}

}

IF (count> printcount) {

Process (0, Count * 100L / Textsize);

Process (1, PNUM Count * (long) all / textsize;

PRINTCOUNT = 1024;

}

}

Process (0,99);

Process (1, PNUM ALL);

}

// Decoding Call

Int Exact (Char * S1, Char * S2, INT PNUM, INT ALL)

{

Char s [100];

Infile = FOPEN (S1, "RB");

IF (Infile == NULL)

{

Sprintf (s, "file% s not found", s1);

Outwindow (s);

Return 1;

}

Sprintf (s, "% s //% s", destpath, s2);

Outfile = FOPEN (S, "WB");

Decode (PNUM, ALL);

Fclose (Infile);

Fclose (Outfile);

Textsize = 0;

CODESIZE = 0;

PRINTCOUNT = 0;

GetBuf = 0;

Getlen = 0;

Putbuf = 0;

PUTLEN = 0;

Return 0;

}

-

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 22:58:46 [Reply]

On the 4th floor

Sender: MARSLV (Dream Life), Letter Area: ProGram Title: Huffman Algorithm (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:42:31 2000), Transmission Sender: Bury Burial), letter area: Programming Title: Huffman Algorithm Send Station: Yi Xian Tempoken Yat-Sen Channel (Wed Apr 19 13:37:43 2000), Station Letter Send Station: BBS Shuimu Tsinghua Station (SAT Feb 26 23:47:50 2000) I wrote a C program, just in the stations of the Chinese workers, there is VC on the stone, just post it, the algorithm process should be the most important, and many of the digital compression has a Huffman algorithm. . # include # include

#include

#include

#include

#include

#include

#include

#include

#define EXIT_OK 0

#define exit_failed -1

//

File * infile, * outfile;

Unsigned long int textsize = 0, CODESIZE = 0, PrintCount = 0;

Void error (char * message)

{

Printf ("/ n% s / n", message);

EXIT (-1);

}

/ * Lzss parameters * /

#define N 4096 / * Size of string buffer * /

#define f 60 /// * Size of Look-ahead buffer 60

#define threshold 2

#define nil n / * end of tree's node * /

Unsigned char

Text_buf [n f -1]; // - 1

Int match_position, match_length,

LSON [N 1], RSON [N 257], DAD [N 1];

Void inittree (void) / * Initializing Tree * /

{

INT I;

For (i = n 1; i <= n 256; i )

RSON [I] = nil; / * root * /

For (i = 0; i

DAD [i] = nil; / * node * /

}

Void InsertNode (int R) / * Inserting Node to the Tree * /

{

INT I, P, CMP;

UNSIGNED Char * Key;

Unsigned C;

CMP = 1;

Key = & text_buf [r];

P = N 1 key [0];

RSON [R] = LSON [R] = NIL;

match_length = 0;

For (;;) {

IF (CMP> = 0) {

IF (RSON [P]! = nil)

P = rson [p];

Else {

RSON [P] = R;

DAD [R] = P;

Return;

}

} else {

IF (LSON [P]! = nil)

P = LSON [P];

Else {

LSON [P] = R;

DAD [R] = P; Return;

}

}

For (i = 1; i

IF ((CMP = Key [I] - text_buf [p i])! = 0)

Break;

IF (i> threshold) {

IF (i> match_length) {

Match_position = ((R - p) & (n - 1)) - 1;

IF ((Match_Length = I)> = f)

Break;

}

IF (i == match_length) {

IF ((C = ((R - P) & (N - 1)) - 1)

Sitoon) {

Match_position = C;

}

}

}

}

DAD [R] = DAD [P];

LSON [R] = LSON [P];

RSON [R] = RSON [P];

DAD [LSON [P]] = R;

DAD [RSON [P]] = R;

IF (RSON [DAD [P]] == P)

RSON [DAD [P]] = R;

Else

LSON [DAD [P]] = R;

DAD [P] = NIL; / * Remove P * /

}

Void deletenode (int P) / * deleding node from the Tree * /

{

INT Q;

IF (DAD [P] == NIL)

Return; / * unregistered * /

IF (RSON [P] == NIL)

Q = LSON [P];

Else

IF (LSON [P] == NIL)

Q = RSON [P];

Else {

Q = LSON [P];

IF (RSON [q]! = nil) {

Do {

Q = rson [q];

} while (rson [q]! = nil);

RSON [Q]] = LSON [q];

DAD [qson [q]] = DAD [q];

LSON [q] = lson [p];

DAD [LSON [P]] = Q;

}

RSON [q] = rson [p];

DAD [RSON [P]] = Q;

}

DAD [q] = DAD [P];

IF (RSON [DAD [P]] == P)

RSON [DAD [P]] = Q;

Else

LSON [DAD [P]] = Q;

DAD [P] = NIL;

}

/ * Huffman Coding Parameters * /

#define n_char (256 - Threshold F)

/ * CHARACTER CODE (= 0..n_Char-1) * /

#define t (n_char * 2 - 1) / * size of table * /

#define r (t - 1) / * root position * /

#define max_freq 0x8000

}

/ * Update When Cumulative Frequency

* /

/ * REACHES to this Value * /

Typedef unsigned char uchar;

/ *

* Tables for encoding / decoding Upper 6 Bits of * Sliding Dictionary Pointer

* /

/ * Encoder Table * /

Uchar p_len [64] = {

0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08

}

Uchar p_code [64] = {

0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,

0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9c,

0xA0, 0xA4, 0xA8, 0xAc, 0xB0, 0xB4, 0XB8, 0XBC,

0xc0, 0xc2, 0xc4, 0xc6, 0xc8, 0xca, 0xcc, 0xce,

0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,

0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xea, 0xec, 0xee,

0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,

0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff

}

/ * Decoder Table * /

Uchar d_code [256] = {

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,

0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x09, 0x09, 0x09, 0x09, 0x09, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a, 0x0a,

0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, 0x0b,

0x0c, 0x0c, 0x0c, 0x0c, 0x0d, 0x0d, 0x0d, 0x0d,

0x0e, 0x0e, 0x0e, 0x0e, 0x0f, 0x0f, 0x0f, 0x0f,

0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,

0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,

0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,

0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,

0x18, 0x18, 0x19, 0x19, 0x1a, 0x1a, 0x1b, 0x1b,

0x1c, 0x1c, 0x1d, 0x1d, 0x1e, 0x1e, 0x1f, 0x1f,

0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,

0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,

0x28, 0x28, 0x29, 0x29, 0x2a, 0x2a, 0x2b, 0x2b,

0x2c, 0x2c, 0x2d, 0x2d, 0x2e, 0x2e, 0x2f, 0x2f,

0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,

0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,

}

Uchar d_len [256] = {

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,

}

Unsigned freq [t 1]; / * cumulative freq table * /

/ *

* Pointing Parent Nodes.

* Area [T .. (T N_CHAR - 1)] Are Pointers for Leaves

* /

INT PRNT [T N_CHAR];

/ * Pointing Children Nodes (Son [], SON [] 1) * /

Int Son [T];

Unsigned getbuf = 0;

Uchar getlen = 0;

INT getBit / * get one bit * /

{

INT I;

WHILE (getlen <= 8) {

IF ((i = getc (infile)) <0) i = 0;

GetBuf | = i << (8 - getlen);

Getlen = 8;

}

i = GetBuf;

GetBuf << = 1;

Getlen--

Return (i <0);

}

INT getByte (void) / * get a byte * /

{

Long Int i;

WHILE (getlen <= 8) {

IF ((i = getc (infile)) <0) i = 0;

GetBuf | = i << (8 - getlen);

Getlen = 8;

}

i = GetBuf;

GetBuf << = 8;

Getlen - = 8;

Return (I >> 8);

}

Unsigned putbuf = 0;

Uchar PUTLEN = 0;

Void Putcode (int L, unsigned C) / * Output c bits * /

{

Putbuf | = C >> PUTLEN;

IF ((PUTLEN = L)> = 8) {

PUTC (Putbuf >> 8, Outfile); IF ((PUTLEN - = 8)> = 8) {

PUTC (Putbuf, Outfile);

CODESIZE = 2;

PUTLEN - = 8;

Putbuf = c << (l - poweren);

} else {

Putbuf << = 8;

CODESize ;

}

}

}

/ * Initialize Freq Tree * /

Void startHUFF ()

{

INT I, J;

For (i = 0; i

FREQ [i] = 1;

SON [i] = i t;

PRNT [i T] = i;

}

i = 0; j = n_char;

While (j <= r) {

FREQ [J] = freq [i] freq [i 1];

SON [J] = i;

PRNT [I] = PRNT [i 1] = j;

i = 2; J ;

}

FREQ [T] = 0xffff;

PRNT [R] = 0;

}

/ * Reconstruct Freq Tree * /

Void reconst ()

{

INT I, J, K;

Unsigned f, L;

/ * Halven Cumulative Freq for Leaf Nodes * /

J = 0;

FOR (i = 0; i

IF (SON [i]> = t) {

FREQ [J] = (FREQ [I] 1) / 2;

SON [J] = SON [I];

J ;

}

}

/ * Make a tree: first, connect children nodes * /

For (i = 0, j = n_char; j

K = i 1;

f = freq [j] = freq [i] freq [k];

FOR (k = j - 1; f

K ;

L = (j - k) * 2;

/ * MOVMEM () is Turbo-C Dependent

ReWritten to Memmove () by kenji * /

/ * MOVMEM (& FREQ [K], & FREQ [K 1], L); * /

(void) Memmove (& FREQ [K 1], & FREQ [K], L);

FREQ [k] = f;

/ * MOVMEM (& Son [K], & Son [K 1], L); * /

(void) Memmove (& Son [K 1], & Son [K], L);

SON [K] = i;

}

/ * Connect Parent Nodes * /

FOR (i = 0; i

IF ((k = SON [i])> = t) {

PRNT [K] = I;

} else {

PRNT [K] = PRNT [K 1] = I;

}

}

}

/ * Update Freq Tree * /

Void Update (int C) {

INT I, J, K, L;

IF (Freq [R] == Max_FREQ) {

Reconst ();

}

C = prNT [C T];

Do {

K = freq [c];

/ * Swap nodes to keep the tree freq-order * /

IF (k> freq [l = c 1]) {

While (K> FREQ [ L]);

L -;

FREQ [C] = FREQ [L];

FREQ [L] = K;

i = SON [C];

PRNT [I] = L;

IF (i

J = SON [L];

SON [L] = i;

PRNT [J] = C;

IF (j

SON [C] = J;

C = L;

}

} while ((c = prNt [c])! = 0); / * do it until Reaching the root * /

}

UNSIGNED CODE, LEN;

Void EncodeChar (unsigned C)

{

UNSIGNED I;

INT J, K;

i = 0;

J = 0;

K = prNT [C T];

/ * Search Connections from Leaf Node to the root * /

Do {

I >> = 1;

/ *

IF Node's Address Is Odd, Output 1

Else Output 0

* /

IF (k & 1) i = 0x8000;

J ;

} while ((k = prNt [k])! = r);

Putcode (j, i);

Code = i;

LEN = J;

Update (c);

}

Void EncodePosition (unsigned C)

{

UNSIGNED I;

/ * OUTPUT UPPER 6 BITS with encoding * /

I = C >> 6;

Putcode (p_len [i], (unsigned) p_code [i] << 8);

/ * OUTPUT LOWER 6 BITS DIRECTLY * /

Putcode (6, (C & 0x3F) << 10);

}

void encodend ()

{

IF (Putlen) {

PUTC (Putbuf >> 8, Outfile);

CODESize ;

}

}

Int decodechar ()

{

Unsigned C;

C = SON [R];

/ *

* Start Searching Tree from the root to leaves.

* choose node # (SON []) if INPUT bit == 0

* Else Choose # (SON [] 1) (Input bit == 1)

* /

While (c

C = getBit ();

C = SON [C];

}

C - = T;

Update (c);

Return C;

}

Int decodePosition ()

{

Unsigned I, J, C;

/ * Decode Upper 6 Bits from Given Table * / i = getByte ();

C = (unsigned) D_CODE [i] << 6;

J = D_LEN [I];

/ * Input Lower 6 bits Directly * /

J - = 2;

While (j--) {

i = (i << 1) getBit ();

}

RETURN C | I & 0x3F;

}

/ * Compression * /

Void Encode (void) / * encoding / compressing * /

{

INT I, C, LEN, R, S, LAST_MATCH_LENGTH;

FSeek (Infile, 0L, 2);

Textsize = ftell (Infile);

IF (& TextSize, Sizeof Textsize, 1, Outfile <1)

Error ("Unable to Write"); / * Write Size of Original TE

XT /

IF (TextSize == 0)

Return;

Rewind (Infile);

Textsize = 0; / * Rewind and rescan * /

STARTHUFF ();

INITTREE ();

S = 0;

R = N - f;

For (i = S; i

TEXT_BUF [I] = '';

For (len = 0; len

TEXT_BUF [R LEN] = C;

Textsize = len;

For (i = 1; i <= f; i )

INSERTNODE (R - I);

INSERTNODE (R);

Do {

IF (Match_length> LEN)

Match_gength = len;

IF (Match_Length <= threshold) {

match_length = 1;

Encodechar (Text_buf [R]);

} else {

EncodeChar (255 - Threshold Match_length);

EncodePosition; Match_Position;

}

Last_match_length = match_length;

For (i = 0; i

(c = getc (infile))! = EOF; i ) {

DELETENODE (S);

TEXT_BUF [S] = C;

IF (S

TEXT_BUF [S N] = C;

S = (S 1) & (n - 1);

R = (R 1) & (n - 1);

INSERTNODE (R);

}

IF ((TextSize = I)> PrintCount) {

Printf ("% 12LD / R", TextSize);

PRINTCOUNT = 1024;

}

While (i

S = (S 1) & (n - 1);

R = (R 1) & (n - 1);

IF (--LEN) INSERTNODE (R);

}

WHILE (LEN> 0);

Encodend ();

Printf ("INPUT:% LD BYTES / N", TextSize);

Printf ("OUTPUT:% LD BYTES / N", CODESize;

}

Void Decode (int pnum, int all) / * decoding / uncompressing * /

{

INT I, J, K, R, C;

Unsigned long int count;

IF (& Textsize, Sizeof Textsize, 1, Infile <1)

Error ("Unable to read"); / * read size of Original Text * /

IF (TextSize == 0)

Return;

STARTHUFF ();

For (i = 0; i

TEXT_BUF [I] = '';

R = N - f;

For (count = 0; count

C = decodeChar ();

IF (c <256) {

PUTC (C, OUTFILE);

Text_buf [R ] = C;

R & = (n - 1);

COUNT ;

} else {

I = (r - decodePosition () - 1) & (n - 1);

J = C - 255 Threshold;

For (k = 0; k

C = TEXT_BUF [(i K) & (n - 1)];

PUTC (C, OUTFILE);

Text_buf [R ] = C;

R & = (n - 1);

COUNT ;

}

}

IF (count> printcount) {

Process (0, Count * 100L / Textsize);

Process (1, PNUM Count * (long) all / textsize;

PRINTCOUNT = 1024;

}

}

Process (0,99);

Process (1, PNUM ALL);

}

// Decoding Call

Int Exact (Char * S1, Char * S2, INT PNUM, INT ALL)

{

Char s [100];

Infile = FOPEN (S1, "RB");

IF (Infile == NULL)

{

Sprintf (s, "file% s not found", s1);

Outwindow (s);

Return 1;

}

Sprintf (s, "% s //% s", destpath, s2);

Outfile = FOPEN (S, "WB");

Decode (PNUM, ALL);

Fclose (Infile);

Fclose (Outfile);

Textsize = 0;

CODESIZE = 0;

PRINTCOUNT = 0;

GetBuf = 0; getlen = 0;

Putbuf = 0;

PUTLEN = 0;

Return 0;

}

-

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:00:35 [Reply]

On the 5th floor

Sender: Marslv (Dream Life), Letter Area: Program Title: Minimum Spanning Tree (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:30:24 2000), the minimum span tree is data An important application of the structure in the structure, its requirements are from one of the rolled outless complete pictures and make this figure still connect (also get a spanning tree), but also consider The amount of trees is minimal. In order to get the minimum spanning tree, people have designed a lot of algorithms, the most famous PRIM algorithm and Kruskal algorithm. The PRIM algorithm is introduced in the textbook, but it is not more detailed enough to understand, in order to help you better understand this algorithm, this article has made further refinement in the book, hoping to help everyone. Suppose V is a collection of vertices in the figure, E is a collection of edges in the figure, and Te is the set of edges in the minimum spanning tree, then the PRIM algorithm can obtain minimum spanning trees by the following steps: 1: Initialization: u = {u 0} , TE = {}. This step sets only a node set U and an empty border TE as a minimum generating tree, in the subsequent algorithm, this stage is constantly changing until the minimum generation Tree. 2: In all U ∈, v ∈V-U sides (U, V) ∈E, find a smallest edge (U 0, V 0), add this side to the set TE, and will The non-U central point of the side is added to the U. The function of this step is to find a side in the border E, requiring this side to meet the following conditions: The first two vertices should be in the vertex set U and V-U, the weight is minimal. After finding this side, put this edge into the side set TE and add this side of the one in the U in the U. This step should be performed multiple times in the algorithm, each execution, the set te and u will change, add one side and a vertex, so TE and U are two dynamic collections, this is in understanding algorithm Pay close attention. 3: If u = V, the algorithm ends; otherwise step 2 repeats. This step can be seen as a cyclic termination condition. We can calculate when u = V, step 2 has executed N-1 time (set N as the number of vertices in the figure), and the N-1 is also increased in TE. This N-1 is needed. The sides of the minimally generated tree. After understanding the basic idea of ​​the Prim algorithm, let's take a look at the specific algorithm. In order to keep the textbooks, we still specify that the connection network is represented by the neighboring matrix NET. If there is no side between the two vertices, the weight is allowed to allow the maximum value within the computer, otherwise it is the weight of the corresponding edge. First define data types: Type Adjmatrix = Array [1. .n, 1..n] of real; // Define a matrix type Adjmatrix of N * N to store adjacent matrices // Edge = Record Beg, EN: 1..n; Length: REAL; END; / / Definition The side storage structure is EDGE, where beg is the starting point of the side, the EN is the end point of the side, the length is the weight of the side // Treetype = array [1..n-1] of edge; // Define a base type for EDGE The array type Treetype, its element is N-1 // var Net: Adjmatrix; / / Defines a variable NET of an Adjmatrix type NET, and the neighbor matrix of the figure is stored in the NET // tree: Treetype; // Define one Treetype type Variable Tree, the information of the N-1 edge can be stored in Tree, including start, end points, and weight.

After the end of the algorithm, the N-1 strip of the minimum tree is stored in the Tree // algorithm as follows (set N as a starting point): Procedure Prim (Net: AdjmaMatrix; VAR Tree: Treetype); // Process header. The meaning of the parameter is: the adjacency matrix of the value NET transfer diagram, the parametric Tree indicates the storage address of the minimum spanning tree // begin for v: = 1 to n-1 do // This loop will open the vertex n- and other N- The N-1 sides of the 1 top point is stored in the variable Tree // [Tree [V] .beg: = n; Tree [V] .en: = v; Tree [v] .length: = net [v] ] For k: = 1 to n-1 do // Step 2 in this loop execution algorithm idea, the cyclic body is executed once, TE will increase one, in the algorithm, this increased edge is placed in the variable Tree On the kth element, it can be considered that the information of TE and U are stored from the first to the K element in TEE. Note: In the algorithm idea, we specifically remind the dynamic state of TE and U, in the algorithm, this dynamic is reflected in the change of the circulating variable k. // [min: = Tree [k] .length; for j: = k to n-1 do if Tree [J] .length [min: = tree [j] .length;

m: = j;]

// The above two statements are used to search for the smallest side of the search weight.

v: = tree [m] .en;

// This statement records the end of the side of the side just added to the TE, that is, the vertices of U -//////////

Edge: = Tree [M];

Tree [M]: = Tree [k];

Tree [K]: = Edge

// The above sentence is used to store the first side of the number to the CNE element of the variable Tree // /

For j: = k 1 to n-1 do

// This loop is used to update the K 1 to N-1 elements in Tree. EN children in these elements after updating

The items are different, and all of them are collectible V-U; Beg child can be the same, but they need to meet two

Condition: First, it should belong to a collection u; another is the side of Beg sub-item and EN children, in all with vertex en contact

The weight should be minimal. //

[D: = Net [v.tree [j] .en];

IF D

THEN [Tree [J] .length: = D;

Tree [J] .beg: = v;]

]

]

For J: = 1 to N-1 DO

// This cycle is used to output a minimum tree //

Writeln (Tree [J] .beg, Tree [J] .en, Tree [J] .length;

END;

The exquisiteness of this algorithm is the decomposition of the problem with the smallest weight (it is also because of this

Solution, resulting in difficulties in algorithm understanding). According to routine ideas, this problem should be solved this:

Take a vertical from the set V-U and U, find the weight of the two vertices, set V-U from the adjacent matrix

There is a M top point in the U, there is N top points, you need to find M * n weight, in this M * n weight, then find the right

Minimal side. Every time the loop is executed, this process should be repeated once, and the amount is relatively large. and

This algorithm utilizes some of the ratios of the C 1 to N-1 in the Tree of Tree to store some of the previous cycles.

As a result, if the element K 1 is an example, it is stored in a set U in a set of vertices to the side of Tree.en,

This edge is the smallest side of all the weights of this point, so the problem of the smallest side, by comparison

The magnitude of the weight of the K 1 to Nth -1 elements can be solved, and each cycle is only compared to N-K-2 times.

It is therefore greatly reduced.

-

. / | /

~ -.` / | .- ~ _` ./-./. - ~ /

`- '/ ~~ -. ~ /

. - ~ / | `-._ /~~-.~ - ~

/ | / ~ -. _ /

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:03:32 [Reply]

On the 6th floor

Circular Redundancy CRC Algorithm Analysis and Program Implementation of Southwest Jiaotong University Computer and Communication Engineering, Liu Dong abstract communication is to transmit information and reliably to each other, so requiring a communication system to transmit messages must be reliable and fast, Reliable and fast in digital communication systems are often a pair of contradictions. In order to solve reliability, communication systems use error control. This paper details the error control principle of cyclic redundancy check CRC (Cyclic Redundancy CHECK) and its algorithm implementation. Keyword communication cycle redundancy check CRC-32 CRC-16 CRC-4 Overview Reliable and fast in digital communication systems is often a pair of contradictions. If it is required to be fast, it will inevitably make each data symbol occupy the time, the waveform is narrowed, the energy is reduced, thereby increasing the possibility of incorrectly after being interfered, and the reliability of transmitting information is lowered. If reliable is required, the transmission message is slowed down. Therefore, how to reasonably resolve the reliability and speed this pair of contradictions, is one of the key issues that correctly design a communication system. In order to ensure the correctness of the transmission process, it is necessary to perform errors control over the communication process. The most common method of error control is to automatically request the retransmission mode (ARQ), forward error correction mode (FEC) and mixed error correction (HEC). When the transmission process is relatively low, it is ideal with FEC mode. When the transmission process is high, it is easy to "chaos" phenomenon using FEC. HEC mode The combination of ARQ and FEC. In many digital communication, ARQ mode is widely used, and the error control at this time only needs to detect the error. There are many error-controlled methods that implement the error detection function. Traditional: parity, checksum detection, repetition check, expansion code check, row redundancy check, etc., these methods are redundant The balance is sent to the receiving end together. The received data is the same verification, and then the resulting check code is compared to the received check code, if the two consistent, it is considered to be correct. But these methods have their own disadvantages, and the probability of misjudgment is relatively high. The cycle redundancy check CRC (CYCLIC Redundancy Check) is a branch of the packet line, and its main application is a binary code group. The encoding is simple and the error probability is very low, and a wide range of applications are obtained in the communication system. The following focuses on the principle of CRC verification and its algorithm implementation. First, the Circulatory Redundancy Rating Code (CRC) CRC check is made of polynomial coding method. The processed data block can be seen as a n-order binary polynomial, by. As an 8-bit binary number 10110101 can be represented as:. The polynomial multiplier operation process is the same as the normal algebraic polynomial. Multi-class add-oriented operations are not in 2 as 2 as the mold, and the addition or subtraction is not in, misplaced, and logical varying or calculation. When using a CRC check, the sender and the receiver use the same generated polynomial G (X), and the first bit of G (x) must be 1. The method of processing the CRC is that the sender removes T (X) by g (x) to obtain the remainder as a CRC check code. When the calibration is calculated as 0, it is determined whether the data frame is wrong. The CRC check can be detected by 100% of all odd random errors and lengths of less than or equal to K (k as g (x) steps). Therefore, the higher the class of the CRC generated polynomial, the smaller the probability of misjudgment. CCITT recommends: 2048 kbit / s PCM base group equipment uses a CRC-4 solution, and the CRC check code used is generated in polynomial G (X) =. With a 16-bit CRC check, it can be guaranteed that only one unspected error is only included in the Bit symbol.

In the frame test sequence FCS of the IBM Synchronous Data Link Control Procedure SDLC, use CRC-16, which generates polynomial G (X) =; and the high-grade data link control procedure for ccitt HDLC frame check sequence FCS In, CCITT-16 is used, which generates polynomial g (x) =. CRC-32 generated polynomial g (x) =. The probability of the CRC-32 error is lower than that of CRC-16. Due to the reliability of CRC-32, the CRC-32 is used for important data transmission, so it is widely used in communication, computers. In some UART communication control chips (such as MC6582, Intel8273, and Z80-Si), CRC check code is used for error control; Ethernet card chips, MPEG decoding chips, also using CRC-32 in error control. Second, the algorithm of CRC check code Analysis The encoding method of the CRC check code is to divide the binary data T (X) to be transmitted to generate a polynomial G (X), and the last remainder is used as the CRC check code. The present step is as follows: The data block that is sent is the b binary polynomial T (X) of the M bit, generating a polynomial as a g (x). RO 0 is added at the end of the data block, and the length of the data block is increased to the M R bit, and the corresponding binary polynomial is. Using the generated polynomial G (X), the remainder is the binary polynomial y (x) of the order of the order of R-1. This binary polynomial y (x) is T (X) to generate a CRC check code encoded by polynomial G (X). The Y (x) is subtracted in mode 2 to obtain a binary polynomial. It is a string to be sent to the CRC check code. As can be seen from the CRC encoding rule, the CRC encoding is actually converted to the M-bit binary polynomial T (X) transmitted into a M R bit binary polynomial that can be removed by G (X), so it can be used when decoding The received data removal G (X), if the remaining number is zero, then the transmission process is not error; if the remainder is not zero, there is definitely an error during the transmission process. Many CRC hardware decoding circuits are detected in this way. It can also be seen as a combination of T (X) and CRC check code, so decoding the received binary data removes the R bit data of the tail, which is the original data. In order to understand the encoding process of the CRC check code, the encoding process of the CRC check code is described below with a simple example. Due to the basis of CRC-32, CRC-16, CCITT and CRC-4, only bit numbers and generated polynomial are different. In order to describe simple, an example of CRC encoding is used to illustrate the encoding process of the CRC. The data T (X) of the transmitted data T (X) is 12 bits of binary data 10010001100; the generation polynomial of the CRC-4 is g (x) =, the order R is 4, that is, 10011. First, 4 0 constitutions are added at the end of T (X), and the data block is 1001000111000000. Then use G (x), it is necessary to obtain the remainder y (x). The following table shows the division process.

SmbD number of divisions / g (x) / Residual number 0 1 00100000000 1 001 0 0001000000000000 1 1 00110000000000 100 00001 0 00001000000 2 1 000000 1100 1 0011 0 001100 From the above table, CRC encoding is actually a cycle Displacement model 2 calculation. For CRC-4, we assume that there is a 5 bits register, by repeated displacement and CRC division, the value in the final register is the remainder of the value we require. So the above steps can be described below: // REG is a 5 bits register to set the value in the REG 0. Add R piece after the original data is added 0. while (data untreated) Begin IF (REG first 1) REG = REG XOR 0011. Move the value in the REG one bit left, read into a new data and placed in the position of the REGISTER's 0 bit. The last four of EndReg is the remainder we have requested. This algorithm is simple, easy to implement, and G (x) generated in any length is applicable. Under the case where the data is transmitted, it can be used. But if the data block sent is long, this method is not suitable. It can only handle one data at a time, the efficiency is too low. In order to improve the processing efficiency, 4 bits, 8 bits, 16 bits, 32 bits can be treated once. Since the structure of the processor basically supports processing of 8-bit data, the 8 bit is appropriate at a time. In order to have an intuitive understanding of the optimized algorithm, first change the above algorithm to an angle. In the above example, the encoding process can be regarded as the following process: Since it only requires the remainder, we only look at the last four digits. Constructs a four-bit register REG, the initial value is 0, and the data is moved into REG (0 bits), and the data of REG3 is removed from REG. There is a above algorithm that the REG is 0 when the data is 0 when the data is removed; when the transferred data is 0, the REG does not perform XOR operation with G (X), quite equal to 0000 Xor operation. That is to say, REG and what kind of data is determined by XOR removal. Since there is only one bit, there is a choice. The above algorithm can be described below, // reg is a 4 bits register initialization T [] = = {0011,0000} Place the value in the REG 0. Add R pieces after the original data (data is not processed) Begin shifted the value in the REG left, read into a new data and placed in the position of the REGISTER's 0 bit. REG = REG XOR T [The end] The end algorithm is processed in Bit, and the above algorithm can be extended to 8 bits, i.e., by BYTE, ie CRC-32. Constructs a four Byte's register REG, the initial value is 0x00000000, and the data is subjected to REG0 (0 bytes of REG, similar), and the data of REG3 moves out of REG. Push it in the above algorithm class to determine the REG and what data is made by the above algorithm class. Since there are 8 Bit, there is a choice. The above algorithm can be described as follows: // REG is a 4 Byte register initialization T [] = {...} // Total = 256 items set the value in REG 0. Add R / 8 0 bytes after the original data WHILE (Data Unexreed) Begin shifts the value of the REG left one byte to read a new byte and placed in the position of the 0th Byte of REG.

REG = REG XOR T [The transferred byte] End algorithm is related to the polynomial division properties. If a M-bit multiplicit T (X) is divided by generating polynomial g (x), each bit is implemented (0 = three, CRC-32).

In order to improve the coding efficiency, most of the investigation form method is used in the actual application to complete the CRC-32 check, the following is a subroutine that generates a CRC-32 check.

Unsigned long crc_32_tab [256] = {

0x00000000, 0x77073096, 0xee0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0X0EDB8832, ..., 0x5A05DF1B, 0x2D02EF8D

}; // The pre-calculated parameter table, a total of 256 items, not listed.

Unsigned long generatecrc32 (Char XData * Database, unsigned long gs)

{

UNSIGNED Long OldCrC32;

UNSIGNED Long CRC32;

Unsigned long oldcrc;

Unsigned int carcnt;

CHAR C, T;

OldCrC32 = 0x00000000; // At 0

CHARCNT = 0;

While (len -) {

T = (OldCrC32 >> 24) & 0xff; // The value of the byte to be removed

OldCrc = CRC_32_TAB [T]; / / / / According to the value of the transmitted byte

C = databuf [charcnt]; / / newly moving byte value

OldCrC32 = (OldCrc32 << 8) | C; // Add newly moving byte value in the last byte of the register

OldCrc32 = OldCrc32 ^ OldCrc; // Put the register with the Isolated value XOR operation

CHARCNT ;

}

CRC32 = OldCrC32;

Return CRC32;

}

The parameter table can be calculated on the PC, or it can be done when the program is initialized. Below is a C language subroutine for calculating the parameter table, compiling under Visual C 6.0.

#include

Unsigned long int crc32_table [256];

Unsigned long int ULPOLYNOMIAL = 0x04c11db7;

Unsigned long int REFLECT (Unsigned long int REF, CHAR CH)

{UNSIGNED long int value (0);

/ / Exchange Bit0 and Bit7, Bit1 and Bit6, class push

For (int i = 1; i <(CH 1); i )

{IF (Ref & 1)

Value | = 1 << (CH - I);

REF >> = 1;

Return Value;

}

INIT_CRC32_TABLE ()

{Unsigned long int CRC, TEMP

// 256 values

For (int i = 0; i <= 0xff; i )

{TEMP = Reflect (i, 8);

CRC32_TABLE [I] = TEMP << 24;

For (int J = 0; J <8; J ) {

UNSIGNED Long Int T1, T2;

Unsigned long int flag = crc32_table [i] & 0x80000000; T1 = (CRC32_TABLE [i] << 1);

IF (Flag == 0)

T2 = 0;

Else

T2 = ulpolynomial;

CRC32_TABLE [I] = T1 ^ T2;}

CRC = CRC32_TABLE [I];

CRC32_TABLE [I] = Reflect (CRC32_TABLE [I], 32);

}

}

Conclude

The CRC calibration is widely used in various data check applications due to its simple implementation. It takes less system resources and can be implemented with hardware and is a good means of data transmission error detection.

references

[1] Wang Xinmei Xiao Guo Town. Error Correction Code - Principle and Method. Xi'an: Xi'an University of Electronic Science and Technology Press, 2001

[2] Luo Wei Xiong Han Li original Dongchang Ding Zhijie Communication principle and circuit. Beijing: Beijing University of Science and Technology Press, 1999

[3] Wang Zhongwen ARQ Coding Communication. Beijing: Machinery Industry Press, 1991

[4] Ross Williams, a Painless Guide To CRC Error Detection Algorithms. Document URL:

Http://www.repairfaq.org/filipg/, 1993

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:04:44 [Reply]

Granter

Sender: Marslv (Fantasy Life), Letter Area: Program Title: Lzari Source Codes (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:36:12 2000), transfer sender: Cloudy (Endless waltz), the letter area: Programming Title: LZARI Source Code Send Station: Yi Xian Time and Space Yat-Sen Channel (WED APR 19 18:00:01 2000), the station letter is a data encoded by LZSS Adaptable 0th-order Arithmetic encoding program. A little higher than the compression ratio of LZH. / ************************************************** ************* LZARI.C - A Data Compression Program (Tab = 4 spaces) ********************** *************************************** 4/7/1989 Haruhiko Okumura Use, DiStribute, And Modify This Program Freely. PLEELY. PLEELYS. PC-VAN Science Nifty-Serve PAF01022 CompuServe 74050, 1022 ********************************* ******************************************************************** / #InClude

#include

#include

#include

/ ********** BIT I / O ********** /

File * infile, * outfile;

Unsigned long int textsize = 0, CODESIZE = 0, PrintCount = 0; void error (char * message)

{

Printf ("/ n% s / n", message);

EXIT (exit_failure);

}

Void Putbit / * Output One Bit (bit = 0, 1) * /

{

Static unsigned int buffer = 0, MASK = 128;

IF (bit) buffer | = mask;

IF ((MASK >> = 1) == 0) {

IF (PUTC (Buffer, Outfile == EOF) Error ("WRITE ERROR");

Buffer = 0; Mask = 128; CODESize ;

}

}

Void flushbitbuffer (void) / * send remaining bits * /

{

INT I;

For (i = 0; i <7; i ) Putbit (0);

}

INT getBit / * get one bit (0 or 1) * /

{

Static unsigned int buffer, mask = 0;

IF ((MASK >> = 1) == 0) {

Buffer = Getc (Infile); Mask = 128;

}

Return ((Buffer & Mask)! = 0);

}

/ ********** lzss with multiple binary trees ********** /

#define N 4096 / * Size of Ring Buffer * /

#DEFINE F 60 / * UPPER LIMIT for Match_length * /

#define threshold 2 / * Encode string inop position and length

IF match_length is get

r th

N this * /

#define nil n / * index for root of binary search t

Rees

* /

Unsigned char text_buf [n f - 1]; / * Ring Buffer of size n,

With extra f-1 bytes to facilitate string Comparison

* /

Int match_position, match_length, / * of longeest match. these A

RE

Set by the insertnode () procedure. * /

LSON [N 1], RSON [N 257], DAD [N 1]; / * Left & Right Chi

LDRE

&

Parents - the constentute binary search tree. * /

Void Inittree (void) / * Initialize Trees * /

{

INT I;

/ * For i = 0 to n - 1, rson [i] and lson [i] Will be the right and

Left children of node i. these Nodes Need Not Be Initialized.Also, Dad [I] is The Parent of Node i. Thase Are Initialized to

NIL (= n), Which Stands for 'Not used.'

For i = 0 to 255, RSON [N i 1] is the root of the tree

For strings this beginning with character i. Thase Are Initialized

To Nil. Note The 406 Trees. * /

For (i = n 1; i <= n 256; i ) rson [i] = nil; / * root * /

For (i = 0; i

}

Void InsertNode (Int r)

/ * INSERTS STRING OF Length F, Text_buf [R..R F-1], INTO One of the

Trees (Text_Buf [R] 'TH TREE) And Returns The Longeest-Match Positio

n

And Length Via The Global Variables Match_Position and

Match_length.

IF match_length = f, The Removes the old node in favor of the ne

w

One, Because the old one will be deleted sooner.

Note R Plays Double Role, As Tree Node and Position In Buffer. * /

{

INT I, P, CMP, TEMP;

UNSIGNED Char * Key;

CMP = 1; key = & text_buf [r]; p = n 1 key [0];

RSON [R] = LSON [R] = NIL; Match_Length = 0;

For (;;) {

IF (CMP> = 0) {

IF (RSON [P]! = NIL) P = rson [P];

Else {RSON [P] = R; DAD [R] = P; Return;}

} else {

IF (LSON [P]! = NIL) P = LSON [P];

Else {LSON [P] = R; DAD [R] = P; Return;}

}

For (i = 1; i

IF ((CMP = Key [i] - text_buf [p i])! = 0) Break;

IF (i> threshold) {

IF (i> match_length) {

Match_position = (r - p) & (n - 1);

IF ((Match_length = I)> = f) Break;

} else if (i == match_length) {

IF ((Temp = (R - P) & (N - 1))

ION)

Match_position = TEMP;

}

}

DAD [R] = DAD [P]; LSON [R] = LSON [P]; RSON [R] = RSON [P];

DAD [LSON [P]] = R; DAD [RSON [P]] = R;

IF (RSON [DAD [P]] == P) RSON [DAD [P]] = R;

Else Lson [DAD [P]] = R;

DAD [P] = NIL; / * Remove P * /

}

Void deletenode (int P) / * delete node p from tree * /

{

INT Q;

IF (DAD [P] == NIL) Return; / * not in Tree * /

IF (RSON [P] == NIL) Q = LSON [P];

ELSE IF (LSON [P] == NIL) q = rson [p];

Else {

Q = LSON [P];

IF (RSON [q]! = nil) {

Do {q = rson [q];} while (RSON [q]! = nil);

RSON [DAD [q]] = LSON [q]; DAD [qson [q]] = DAD [q];

LSON [q] = LSON [P]; DAD [LSON [P]] = Q;

}

RSON [q] = rson [p]; DAD [RSON [P]] = Q;

}

DAD [q] = DAD [P];

IF (RSON [DAD [P]] == P) RSON [DAD [P]] = Q;

Else Lson [DAD [P]] = Q;

DAD [P] = NIL;

}

/ ********** Arithmetic compression ********** /

/ * If you are not familia with arithmetic compression, you

reta

I. E. Witten, R. M. NEAL, AND J. G. Cleary,

Communications of The ACM, VOL. 30, PP. 520-540 (198

7),

From Which Much Have Been Borrowed. * /

#define m 15

/ * Q1 (= 2 to the m) MUST Be Sufficiently Large, But Not So

Large as the unsigned long 4 * q1 * (q1 - 1) overflows. * /

#define q1 (1 ul << m)

#define Q2 (2 * q1)

#define q3 (3 * q1)

#define Q4 (4 * q1)

#define max_cum (Q1 - 1)

#define n_char (256 - Threshold F)

/ * CHARACTER CODE = 0, 1, ..., n_char - 1 * /

Unsigned long int low = 0, high = Q4, value = 0;

Int Shifts = 0; / * Counts for Magnifying Low and High Around Q2 * /

INT CHAR_TO_SYM [N_CHAR], SYM_TO_CHAR [N_CHAR 1];

Unsigned INTSYM_FREQ [N_CHAR 1], / * frequency for symbols * /

SYM_CUM [N_CHAR 1], / * Cumulative Freq for Symbols * /

Position_cum [n 1]; / * cumulative freq for positions * /

Void StartModel (Void) / * Initialize Model * /

{

INT CH, SYM, I;

SYM_CUM [N_CHAR] = 0;

For (Sym = n_char; SYM> = 1; SYM -) {

CH = SYM - 1;

CHAR_TO_SYM [CH] = SYM; SYM_TO_CHAR [SYM] = CH;

SYM_FREQ [SYM] = 1;

SYM_CUM [SYM - 1] = SYM_CUM [SYM] SYM_FREQ [SYM];

}

Sym_freq [0] = 0; / * Sentinel (! = SYM_FREQ [1]) * /

Position_cum [n] = 0;

For (i = n; i> = 1; i -)

Position_cum [i - 1] = position_cum [i] 1000 / (i 200);

/ * Empirical Distribution Function (Quite Tentative)

* /

/ * Please devise a better mechanism! * /

}

Void Updatemodel (int SM)

{

INT I, C, CH_I, CH_SYM;

IF (SYM_CUM [0]> = max_cum) {

C = 0;

For (i = n_char; i> 0; I -) {

SYM_CUM [I] = C;

C = (SYM_FREQ [I] = (SYM_FREQ [I] 1) >> 1);

}

SYM_CUM [0] = C;

}

For (i = SYM; SYM_FREQ [I] == SYM_FREQ [i - 1]; I -);

IF (i

CH_I = SYM_TO_CHAR [I]; ch_sym = SYM_TO_CHAR [SYM];

SYM_TO_CHAR [I] = Ch_SYM; SYM_TO_CHAR [SYM] = CH_i;

CHAR_TO_SYM [CH_I] = SYM; char_to_sym [ch_sym] = i;

}

SYM_FREQ [i] ;

While (--i> = 0) SYM_CUM [i] ;

}

Static void Output (int bit) / * Output 1 bit, Followed by ITS

Complements * /

{

Putbit (bit);

For (; shifts> 0; shifts -) Putbit (! bit);

}

Void EncodeChar (int CH)

{

Int Sym;

Unsigned long int range;

SYM = char_to_sym [ch];

Range = high - low;

HIGH = LOW (Range * Sym_cum [SYM - 1]) / SYM_CUM [0];

Low = (Range * SYM_CUM [SM]) / SYM_CUM [0]; for (;;) {

IF (high <= Q2) OUTPUT (0);

Else IF (low> = Q2) {

Output (1); low - = Q2; high - = Q2;

Else if (low> = Q1 && high <= Q3) {

Shifts ; low - = q1; high - = q1;

Else Break;

Low = low; high = high;

}

UpdateModel (SYM);

}

Void encodePosition (int position)

{

Unsigned long int range;

Range = high - low;

High = low (range * position_cum [position]) / position_cum [0];

Low = (Range * Position_cum [Position 1]) / position_cum [0];

For (;;) {

IF (high <= Q2) OUTPUT (0);

Else IF (low> = Q2) {

Output (1); low - = Q2; high - = Q2;

Else if (low> = Q1 && high <= Q3) {

Shifts ; low - = q1; high - = q1;

Else Break;

Low = low; high = high;

}

}

Void EncodeEnd (Void)

{

SHIFTS ;

IF (Low

Flushbitbuffer (); / * flush bits remaining in buffer * /

}

INT binarysearchsym (unsigned int x)

/ * 1 if x> = SYM_CUM [1],

N_char if Sym_cum [n_char]> X,

I Such That Sym_cum [i - 1]> x> = SYM_CUM [i] Otherwise * /

{

INT I, J, K;

i = 1; j = n_char;

While (i

K = (i j) / 2;

IF (SYM_CUM [K]> X) i = k 1; ELSE J = K;

}

Return I;

}

INT BinarySearchPos (unsigned int x)

/ * 0 IF x> = position_cum [1],

N - 1 if position_cum [n]> x,

I Such That Position_cum [i]> x> = position_cum [i 1] Otherwise

* /

{

INT I, J, K;

i = 1; j = N;

While (i

K = (i j) / 2;

IF (position_cum [k]> x) i = k 1; else j = k;}

RETURN I - 1;

}

Void StartDecode (Void)

{

INT I;

For (i = 0; i

Value = 2 * Value getBit ();

}

Int decodeChar (Void)

{

Int Sym, CH;

Unsigned long int range;

Range = high - low;

SYM = binarysearchsym ((unsigned int)

(((Value - Low 1) * SYM_CUM [0] - 1) / RANGE));

HIGH = LOW (Range * Sym_cum [SYM - 1]) / SYM_CUM [0];

Low = (Range * Sym_cum [SYM]) / SYM_CUM [0];

For (;;) {

IF (low> = Q2) {

Value - = Q2; Low - = Q2; HIGH - = Q2;

Else if (low> = Q1 && high <= Q3) {

Value - = Q1; Low - = Q1; HIGH - = Q1;

Else IF (High> Q2) Break;

Low = low; high = high;

Value = 2 * Value getBit ();

}

CH = SYM_TO_CHAR [SYM];

UpdateModel (SYM);

Return ch;

}

INT decodePosition (Void)

{

INT position;

Unsigned long int range;

Range = high - low;

Position = binarysearchPOS ((unsigned int)

(((Value - Low 1) * position_cum [0] - 1) / RANGE));

High = low (range * position_cum [position]) / position_cum [0];

Low = (Range * Position_cum [Position 1]) / position_cum [0];

For (;;) {

IF (low> = Q2) {

Value - = Q2; Low - = Q2; HIGH - = Q2;

Else if (low> = Q1 && high <= Q3) {

Value - = Q1; Low - = Q1; HIGH - = Q1;

Else IF (High> Q2) Break;

Low = low; high = high;

Value = 2 * Value getBit ();

}

Return Position;

}

/ ********** encode and decode ********** /

Void Encode (Void)

{

INT I, C, LEN, R, S, LAST_MATCH_LENGTH;

FSeek (Infile, 0L, Seek_ek_ek; TextSize = ftell (Infile);

IF (& TextSize, Sizeof Textsize, 1, Outfile <1)

Error ("Write Error"); / * Output Size of Text * /

CODESIZE = Sizeof Textsize;

IF (TextSize == 0) Return;

Rewind (Infile); TextSize = 0;

StartModel (); inittree ();

S = 0; r = n - f;

For (i = s; i

For (len = 0; len

TEXT_BUF [R LEN] = C;

Textsize = len;

For (i = 1; i <= f; i ) INSERTNODE (R - i);

INSERTNODE (R);

Do {

IF (Match_length> LEN) match_length = len;

IF (Match_Length <= threshold) {

Match_length = 1; EncodeChar (Text_buf [R]);

} else {

EncodeChar (255 - Threshold Match_length);

EncodePosition (Match_Position - 1);

}

Last_match_length = match_length;

For (i = 0; i

(c = getc (infile))! = EOF; i ) {

Deletenode (s); text_buf [s] = C;

IF (S

S = (S 1) & (n - 1);

R = (R 1) & (n - 1);

INSERTNODE (R);

}

IF ((TextSize = I)> PrintCount) {

Printf ("% 12LD / R", TextSize; printcount = 1024;

}

While (i

DELETENODE (S);

S = (S 1) & (n - 1);

R = (R 1) & (n - 1);

IF (--LEN) INSERTNODE (R);

}

WHILE (LEN> 0);

Encodend ();

Printf ("in:% lu bytes / n", textsize);

Printf ("OUT:% Lu Bytes / N", CODESIZE);

Printf ("out / in:% .3f / n", (double) CODESIZE / TEXTSIZE);

}

Void Decode (Void)

{

INT I, J, K, R, C;

Unsigned long int count; if (& Textsize, Sizeof Textsize, 1, Infile <1)

Error ("Read Error"); / * read size of text * /

IF (TextSize == 0) Return;

StartDecode (); startmodel ();

For (i = 0; i

R = N - f;

For (count = 0; count

C = decodeChar ();

IF (c <256) {

PUTC (C, OUTFILE); Text_buf [R ] = C;

R & = (n - 1); count ;

} else {

I = (r - decodePosition () - 1) & (n - 1);

J = C - 255 Threshold;

For (k = 0; k

C = TEXT_BUF [(i K) & (n - 1)];

PUTC (C, OUTFILE); Text_buf [R ] = C;

R & = (n - 1); count ;

}

}

IF (count> printcount) {

Printf ("% 12lu / R", count); PrintCount = 1024;

}

}

Printf ("% 12lu / n", count);

}

Int main (int Argc, char * argv [])

{

Char * S;

IF (argc! = 4) {

Printf ("'LZARI E File1 File2' Encodes File1 Into File2./N"

"'LZARI D File2 file1' decodes file2 Into file1./

N ");

Return EXIT_FAILURURE;

}

IF ((s = argv [1], s [1] || StrPBRK (S, "DEDE") == NULL)

|| (S = Argv [2], (Infile = FOPEN (S, "RB")) == NULL)

|| (S = Argv [3], (Outfile = FOPEN (S, "WB")) == null)) {

Printf ("???% s / n", s); return exit_failure;

}

IF (TouPper (* Argv [1]) == 'E') encode (); else decode ();

Fclose (Infile); fclose (outfile);

Return EXIT_SUCCESS;

}

-

.- ~ /

/ `- '/.'` -:

| / `._

| | .-. {

/ | `- '`.

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500 Member Information PM E-mail

Published: 2003-10-3 23:07:35 [Reply]

On the 8th floor

Sender: MARSLV (Dream Life), Letter Area: Program Title: LZSS Source Codes (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:36:56 2000), transfer sender: Cloudy (Endless waltz), the letter area: Programming Title: LZSS Source Code Send Station: Yi Xian Time and Space Yat-Sen Channel (WED APR 19 18:02:06 2000), the source code of the station letter LZSS. LZSS is a dictionary-based compression algorithm with a small compression ratio, but the speed is very fast. PLY. PLEASE Send Me Your Improved Versions. PC-Van Science Nifty-Serve PAF01022 CompuServe 74050, 1022 ***************************************** **************************************************** / #include

#include

#include

#include

#define N 4096 / * Size of Ring Buffer * /

#define f 18 / * Upper limited for match_length * /

#define threshold 2 / * Encode string inop position and length

IF match_length is get

R Thhan this * /

#define nil n / * index for root of binary search t

Rees

* /

Unsigned long int

Textsize = 0, / * text size counter * /

CODESIZE = 0, / * code size counter * /

PrintCount = 0; / * Counter for Reporting Progress Every 1k B

Ytes

* /

Unsigned char

TEXT_BUF [N F - 1]; / * Ring Buffer of Size N,

With extra f-1 bytes to facilitate string Comparison

* /

Int match_position, match_length, / * of longeest match. these A

RE

Set by the insertnode () procedure. * /

LSON [N 1], RSON [N 257], DAD [N 1]; / * Left & Right Chi

LDRE

&

Parents - the constentute binary search tree. * /

File * infile, * outfile; / * Input & output files * /

Void Inittree (void) / * Initialize Trees * /

{

INT I;

/ * For i = 0 to n - 1, rson [i] and lson [i] Will be the right and

Left children of node i. these Nodes Need Not Be Initialized.Also, Dad [I] is The Parent of Node i. Thase Are Initialized to

NIL (= n), Which Stands for 'Not used.'

For i = 0 to 255, RSON [N i 1] is the root of the tree

For strings this beginning with character i. Thase Are Initialized

To Nil. Note The 406 Trees. * /

For (i = n 1; i <= n 256; i ) rson [i] = nil;

For (i = 0; i

}

Void InsertNode (Int r)

/ * INSERTS STRING OF Length F, Text_buf [R..R F-1], INTO One of the

Trees (Text_Buf [R] 'TH TREE) And Returns The Longeest-Match Positio

n

And Length Via The Global Variables Match_Position and

Match_length.

IF match_length = f, The Removes the old node in favor of the ne

w

One, Because the old one will be deleted sooner.

Note R Plays Double Role, As Tree Node and Position In Buffer. * /

{

INT I, P, CMP;

UNSIGNED Char * Key;

CMP = 1; key = & text_buf [r]; p = n 1 key [0];

RSON [R] = LSON [R] = NIL; Match_Length = 0;

For (;;) {

IF (CMP> = 0) {

IF (RSON [P]! = NIL) P = rson [P];

Else {RSON [P] = R; DAD [R] = P; Return;}

} else {

IF (LSON [P]! = NIL) P = LSON [P];

Else {LSON [P] = R; DAD [R] = P; Return;}

}

For (i = 1; i

IF ((CMP = Key [i] - text_buf [p i])! = 0) Break;

IF (i> match_length) {

Match_position = P;

IF ((Match_length = I)> = f) Break;

}

}

DAD [R] = DAD [P]; LSON [R] = LSON [P]; RSON [R] = RSON [P];

DAD [LSON [P]] = R; DAD [RSON [P]] = R;

IF (RSON [DAD [P]] == P) RSON [DAD [P]] = R;

Else Lson [DAD [P]] = R; DAD [P] = NIL; / * Remove P * /

}

Void deletenode (int P) / * deletes node p from tree * /

{

INT Q;

IF (DAD [P] == NIL) Return; / * not in Tree * /

IF (RSON [P] == NIL) Q = LSON [P];

ELSE IF (LSON [P] == NIL) q = rson [p];

Else {

Q = LSON [P];

IF (RSON [q]! = nil) {

Do {q = rson [q];} while (RSON [q]! = nil);

RSON [DAD [q]] = LSON [q]; DAD [qson [q]] = DAD [q];

LSON [q] = LSON [P]; DAD [LSON [P]] = Q;

}

RSON [q] = rson [p]; DAD [RSON [P]] = Q;

}

DAD [q] = DAD [P];

IF (RSON [DAD [P]] == P) RSON [DAD [P]] = Q; ELSE LSON [DAD [P]] = Q;

DAD [P] = NIL;

}

Void Encode (Void)

{

INT I, C, LEN, R, S, LAST_MATCH_LENGTH, CODE_BUF_PTR;

Unsigned char code_buf [17], mask

INITTREE (); / * Initialize Trees * /

Code_buf [0] = 0; / * Code_buf [1..16] SAVES Eight Units Of Code, And

Code_buf [0] Works As Eight Flags, "1" Repesenting That the

Unit

Is An Unencoded Letter (1 Byte), "0" a position-and-length p

Air

(2 Bytes). Thus, Eight Units Require At Most 16 bytes of Co

DE.

/

Code_buf_ptr = mask = 1;

S = 0; r = n - f;

For (i = s; i

The Order in Which these strings are inserted. this Way,

Degenerate Trees Will Be Less Likey to Occur. * /

INSERTNODE (R); / * Finally, Insert The Whole String Just Read. The

Global Variables Match_length and match_position is set. * /

Do {

IF (Match_length> LEN) match_length = le; / * match_length

May Be Spuriously Long Near The end of text. * /

IF (Match_Length <= threshold) {

Match_length = 1; / * NOT Long ENOUGH Match. Send O

NE B

TE. * /

Code_buf [0] | = mask; / * 'send one byte' flag * /

Code_buf [code_buf_ptr ] = text_buf [r]; / * Send UNC

Oded

* /

} else {

Code_buf [code_buf_ptr ] = (unsigned char) match_pos

iTio

;

Code_buf [code_buf_ptr ] = (unsigned char)

(((Match_Position >> 4) & 0xF0)

| (Match_length - (Threshold 1))))))))))))))))))))); / * Send Posi

Tion

and

LENGTH PAIR. NOTE MATCH_LENGTH> THR

Esho

D. * /

}

IF ((Mask << = 1) == 0) {/ * Shift Mask Left One bit. * /

For (i = 0; I

8 un

Ts of * /

PUTC (Code_BUF [I], Outfile; / * Code Toge

Ther

* /

CODESIZE = Code_buf_ptr;

Code_buf [0] = 0; code_buf_ptr = mask = 1;

}

Last_match_length = match_length;

For (i = 0; i

(c = getc (infile))! = EOF; i ) {

Deletenode (s); / * delete old strings and * /

Text_buf [s] = c; / * read new bytes * /

IF (S

Ion

s

Near the end of buffer, extend the buffer to

MAK

String Comparison Easier. * /

S = (S 1) & (n - 1); r = (R 1) & (n - 1); / * Since this is a ring buffer, Increment th

e poo

Ition

MODULO N. * /

INSERTNODE (R); / * register the string in text_buf [r

. .r

-1] */

}

IF ((TextSize = I)> PrintCount) {

Printf ("% 12LD / R", TextSize; printcount = 1024;

/ * Reports Progress Each Time The Textsize E

Xcee

s

Multiples of 1024. * /

}

While (i

TEXT

* /

DELETENODE (S); / * N

o NE

D to read, but * /

S = (S 1) & (n - 1); r = (r 1) & (n - 1);

IF (--LEN) INSERTNODE (R); / * Buffer MA

Y NO

BE EMPTY. * /

}

WHILE (LEN> 0); / * Until Length of String to Be Processed IS

zer

* /

IF (code_buf_ptr> 1) {/ * send remaining code. * /

For (i = 0; i

);

CODESIZE = Code_buf_ptr;

}

Printf ("in:% ld bytes / n", textsize; / * encoding is done. * /

Printf ("OUT:% LD BYTES / N", CODESIZE);

Printf ("out / in:% .3f / n", (double) CODESIZE / TEXTSIZE);

}

Void decode (void) / * Just the reverse of eNCode (). * /

{

INT I, J, K, R, C;

Unsigned int flags;

For (i = 0; i

R = N - f; Flags = 0;

For (;;) {

IF ((Flags >> = 1) & 256) == 0) {

IF ((c = getc) == EOF) Break;

Flags = c | 0xff00; / * Usess Higher Byte

CLEV

RLY * /

} / * T

O Co

NT Eight * /

IF (Flags & 1) {

IF ((c = getc) == EOF) Break;

PUTC (C, OUTFILE); Text_buf [R ] = C; R & = (N - 1);} else {

IF ((i = getc (infile)) == EOF) Break;

IF ((j = getc (infile)) == EOF) BREAK;

i | = ((j & 0xf0) << 4); j = (j & 0x0f) threshold;

FOR (k = 0; k <= j; k ) {

C = TEXT_BUF [(i K) & (n - 1)];

PUTC (C, OUTFILE); Text_buf [R ] = C; R & =

(N -

1);

}

}

}

}

Int main (int Argc, char * argv [])

{

Char * S;

IF (argc! = 4) {

Printf ("'lzss e file1 file2' encodes file1 Into file2./N"

"'LZSS D file2 file1' decodes file2 Into file1./n

");

Return EXIT_FAILURURE;

}

IF ((s = argv [1], s [1] || StrPBRK (S, "DEDE") == NULL)

|| (S = Argv [2], (Infile = FOPEN (S, "RB")) == NULL)

|| (S = Argv [3], (Outfile = FOPEN (S, "WB")) == null)) {

Printf ("???% s / n", s); return exit_failure;

}

IF (TouPper (* Argv [1]) == 'E') encode (); else decode ();

Fclose (Infile); fclose (outfile);

Return EXIT_SUCCESS;

}

-

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:11:59 [Reply]

Grace

Sender: MARSLV (Dream Life), Letter Area: Program Title: RC5 Algorithm (Transfer) Send Restaurant: BBS Shantou University Tulip Station (Sun Oct 22 00:33:08 2000), transferred: RC5 algorithm Letter: Yi Xian Time and Space Yat-Sen Channel (sat apr 22 00:11:30 2000), one of the most commonly used grouping algorithms in the station, using the maximum length of 256 bytes. RC5 accepts two parameters R: The number of cycles, B: Calculate the password length in Word. Initialized subkey number S [2 * r 2]: definition P = 0xB7E15163, Q = 0x9e3779b9 s [0] = p, s [i] = (s [i 1] q) mod power (2, w ); i = j = 0; a = b = 0; cycle 3 * max (2 * r 2, b) followed by: a = s [i] = rol ((S [i] a b) , 3) B = K [J] = ROL ((K [J] A B), (A B)); i = (i 1) MOD 2 * R 2 J = (J 1) MOD B encryption algorithm: Frangxt text M [2] of 2WORDS is made by ciphertext C [2] C [0] = m [0] s [0]; C [1] = m [1] S [1]; for i = 1 to r C [0] = rol ((C [0] xor C [1]), C [1]) S [2 * i] C [1] = ROL (C [1] XOR C [0]), M [0]) S [2 * i 1] Decryptive algorithm: Ciphertext C [2] for 2WORDS as the following transformation, to obtain a plaintext M [2] For i = r downto 1 c [1] = ROR ((C [1] -s [2 * i 1], C [0]) xor C [0] C [0] = ROR ((C [0] -S [2 * i], c [1]) xor c [1] endfor m [1] = C [1] -s [1] M [0] = C [0] -s [0] - all Huiyi Xingqiang Flying in Qingtian City Moon This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:13:47 [Reply]

On the 10th floor

Sender: MARSLV (Dream Life), Letter Area: Program Title: WIN95 PWL File Password Encryption Algorithm (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:31:51 2000), transfer Win95 PWL The file password encryption algorithm has recently studied the PWL file of WIN95 / WFWG3.11, because there have been a glide.c program to solve some resources of the PWL file, but it can't give Password. With Softice, I have followed it. Discovery The code involved in Password is in MSPWL32.DLL, the following program is translated into C to C. Despite the completion of the algorithm, the method of cracking is not big (I think a good encryption algorithm should be a better decryption method that is better than poor act, if a prawn has a good crack method, you may wish to come on POST Discussion in discussions) But this Password gets the method only if there is technical significance. After all, it is not possible to get root privilege, but only someone's Preference Settings! :- (some explanation of the PWL file: 14 characters long password (all turn For uppercase), use it to generate a 32-bit key, to obtain a XOR string by the following algorithm, next to this xor string xor 20 Bytes long username (also transferred to uppercase), the result is available for PWL file OFFSET 0x208- 0x21b, 0x21c starts for a series of pointers that point to the hair string (of course already over). Saved in the resource string is mainly the password of some of the USER's Shared Directory, the resource string also with the xor string xor, PWL file. / / ================= crypt.cpp 1997.8.16 ================ # include # include # include

#include

/ * The WFWG3.11 / Win95's PWL File Crypt Algorithm DemonStration:

Codes extracted from /win95/system/mspwl32.dll

You May Use Softice to Trace It or W32dasm to Disassemble IT,

The Offset Address of Each Routine is listed Below (you May

Find The Corresponding Codes in W32dasm's Alf File According To The

OFFSET VALUE * /

TYPEDEF UNSIGNED CHAR BYTE

Inline void swapbyte (Byte & C1, Byte & C2)

{

BYTE TEMP;

TEMP = C1;

C1 = C2;

C2 = TEMP;

}

// generate a 32 bit key accounting to the password (capital)

// translate from mspwl32.dll's cots beginning at 7fcb1972h

Unsigned long generatekeyKey (Char * Pw)

{

INT I, LEN;

Unsigned long sum = 0;

Len = Strlen (PW);

For (i = 0; i <= le; i )

{

SUM = Toupper (pw [i]); sum = (sum << 0x7) | (SUM >> 0x19);

// Same as Rol Sum, 7

}

Return SUM;

}

// translate from mspwl32.dll's cots beginning at 7fcb1000h

Void GenerateStream (Byte * Stream, Unsigned Long Key)

{

BYTE Keychar [4];

INT I, J, Shift = 0;

BYTE INDEX = 0;

* (UNSIGNED Long *) keychar) = key;

For (i = 0; i <256; i )

Stream [i] = (byte) i;

For (i = 0; i <256; i )

{

Index = Keychar [Shift] stream [i];

SwapByte (stream [i], stream [index]);

Shift = (shift 1)% 4;

}

}

// translate from mspwl32.dll's cots beginning at 7fcb1088h

Void generatexorstring (byte * src, byte * DEST)

{

BYTE J = 0, Index;

INT I;

For (i = 1; i <= 255; i )

{

J = SRC [I];

SwapByte (SRC [I], SRC [J]);

INDEX = SRC [i] src [j];

DEST [I-1] = SRC [INDEX];

}

}

Int main (int Argc, char * argv [])

{

UNSIGNED Long Key;

BYTE TABLE [256];

Byte xorstr [256];

INT I, LEN;

IF (Argc <3)

{

Printf ("USAGE: CRYPT Username Password / N");

Printf ("Author: RANER, DCS, TSINGHUA UNIV / N");

Printf ("Comment: this program is buy to demonstrate the win95

PWL File Crypt / N ");

Printf ("Method. You May Compare The Crypted Username

String with the / n ");

Printf ("String Beginning At Offset 0x208 of PWL file.

/ N ");

Return 1;

}

Key = generatekey (Argv [2]);

Printf ("/ N32 BITS Key: / N 0x% 08LX / N", KEY);

GenerateStream (Table, Key);

Generatexorstring (Table, Xorstr);

Printf ("/ nxor string:");

For (i = 0; i <54; i )

{

IF (i% 16 == 0) Printf ("/ n");

Printf ("% 02x,", xorstr [i]);

}

Printf ("... / n");

LEN = Strlen (Argv [1]); for (i = 0; i

Xorstr [i] ^ = (byte) TouPper (Argv [1] [i]);

Printf ("/ ncrypted username: / n");

For (i = 0; i <20; i )

Printf ("% 02x% C", xorstr [i], i == 19? '/ n': ',');

/ * You May Debug UserName.PWL & D 308 To Verify ITS Correctness.

Crypted username (20 bytes) is saved at offset 0x208 of * .pwl * /

Return 0;

}

-

. / | /

~ -.` / |. - ~ _

`./-./. - ~ /

`- '/ ~~ -. ~ /

. - ~ / | `-._ /~~-.~ - ~

/ | / ~ -. _ /

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:15:35 [Reply]

On the 11th floor

Article Source: Baiyun Huanghe ★ Sender: FYD (Ding Ding), Letter Area: Encrypt Title: Decryption and Encryption Send Station: Wuhan Baiyun Huanghe Station (Mon Dec 8 14:11:23 1997), letters title: decryption and encryption of version WPS file: Monthly No. 3 PC applications author: above Cheng University Pu version 5.0 Jinshan DOS software, arrange the "set password" option in the WPS menu, allowing users through a simple operation Encrypt the file that needs to be confidential. However, this feature will also bring us some troubles. For example, when the forgotten password, or because of the wrong operation, enter the password that you can't confirm, etc., will cause difficult to directly read their own files. The knowledge and methods introduced herein will help you solve this problem and tell you how to add more effectively to your WPS file. First, the structure of the WPS file and the encryption process of the WPS user file, the first 1024 bytes of the WPS user file (at 1000h-03FFH) is the various settings of the file, and the various states in the store, where 02DDH-02E4H The 8 bytes are used to store passwords, and the body of the file is stored in the unit after 0400h. The encryption process of the file is as follows: After the user selects the "Set Password" function, the WPS allows the user to enter 1 to 8 characters as password; for the ASCII code of each character typed, WPS first high 4 bits and low 4 The bit swap position, reverse it, and then store the unit starting from 02DDH. For example, when the first character typed for "A", "A" ASCII code is 41h, and the WPS will be swapped at 14 h (the corresponding binary code is 00010100); then press the inverse to: EBH (corresponding binary code is: 11101011); then stores EBH into the 02DDH unit. When each file is stored, the WPS should check the contents of the 02DDH-02E4H unit in advance. If it is not 0, it indicates that the user sets a password to the file, and the WPS will encrypt the text of the file with the content of the 8 units. The method is to start from the 0400H unit, each 8 bytes are set, and the 8 bytes of the cryptographic region are different or the file is completed; then the replication is then executed. If the WPS checks the content of the 02DDH-02E4H unit is all 0, the file is directly stored. Second, the method of decryption knows the above principles, it is easy to solve the problem of forgotten passwords. First, use Debug to transfer files that need to be decrypted into memory. When the file is named: filename.wps, type the following command line: Debug filename.wps ↓ where the location where the debug.com file is stored (usually in the DOS subdirectory); give it to save FileName. The location of the WPS file. If (or) is the current path, the item can be omitted in the command line. After the above instruction is executed, a flashing "-" symbol will appear on the screen, which is the prompt of Debug. Since the file that debug into the memory is stored from the offset address 0100H, the offset address of the cryptographic region is 03DDH-03E4H at this time. We can use the "D" command to view the contents of their passwords; the - prompt, type "": -D 3DD ↓ if the content displayed on the screen is as follows: 55AA: 03D0EB DB CB ... 55AA: 03E000 00 00 00 00 00 E0 01-D0 01 C0 01 B0 01 A0 01 ..................... We can see that there are three password characters in the file, and its 16 credits are: "EB , DB, CB. Get "Be, BD, BC" with the high 4 bits of each byte with the low 4-digit switching position; then calculate the difference between the three numbers to subtract the three numbers, which can be subjected to FFH. "41, 42, 43", check the ASCII code table, which is the ASCII code of three characters of "A, B, C". Use the "Q" instruction to exit Debug.

Start the WPS software, call the filename.wps file, when the WPS requires the password, type "ABC" to enter the file. Third, the method of encryption is known above, the encryption method provided by WPS software is very easy to be deciphered by others. In order to protect the files you need to encrypt more effectively, the method described below can be used. First choose several of the most familiarity, and others are difficult to know as passwords (such as the pinyin heads of their own friends or relatives). For files that need to encrypt, first encrypt with the method provided by WPS; after the storage, use D "D" instruction to view the transformed password content, record it; then use the "E" instruction to rewrite the input password to 00h; use "W" instruction store; finally, use "Q" instruction to exit. For example, when the input password is three characters, the following command line can be typed in the "-" prompt: -E 3DD 00 00 00 ↓ -w ↓ -q ↓ After processed, if some When called, WPS does not ask for a password, but the content displayed will be a pile of difficulty messy symbols (because WPS has passed through the text section). People who try to peep passwords with Debug can only see 00h and cannot be deciphered. When you need to call this file, you can first use Debug's "E" instruction to restore the password according to the original record; then start the WPS, answer the password, and call up the original text. (Author address: Beijing Chaojiazhuang Xili Machinery Engineering College, 100020; Received Date: 1995.12) - 怀 怀 兴 飞 飞 上 青 青 青 天 揽 明 明 飞 飞 飞 飞 飞 飞

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:17:23 [Reply]

12th floor

Sender: laohong (batch), letter area: Program Title: Operating System Scheduling Station: BBS Shantou University Tulip Station (Sun Sep 9 18:44:23 2001), transfer // Operating system scheduling #include #include #include #include #include #define ed NULL void diaodu (void); void shifang (int); typedef struct node_type {// memory chain int start, len, fenp; struct node_type * next;} link; typedef struct dl_type {// Queue INT IP, LEN;} DLS; DLS DL [20]; // Defines the queue INT DLZ = 0 of 20 elements; link * h, * p, * q; link * h, * p, * q INT size, NUM; // Defines the total amount of memory and the number of processes of the process ofstream output ("Output2.txt"); int main () {char * ch = ""; int count; // Define loop variable INT ZJ = 0; IFStream INPUT ("Read2.txt"); Input >> Size >> Num; cout <{input >> DL [DLZ] .ip >> DL [DLZ] .len; cout <{input >> zj; cout > count;} void diaodu () {INT I, L, FF = 0; for (i = 0; i {{p = H; do {if (p-> len> = DL [i] .lend && p-> fenp == 0) {Q = (link *) malloc (limited); Q-> next = p-> next; q-> start = p-> start dl [i ] .lend; q-> len = p-> len-dl [i] .len; q-> fenp = 0; p-> fenp = DL [i] .ip; p-> len = DL [i]. Len; p-> next = q; cout << "<<"

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:19:15 [Reply]

On the 13th floor

Sender: MARSLV (Fantasy Life), Letter Area: Program Title: Fourier Transform Source Sequence (Transfer) Send Station: BBS Shantou University Tulip Station (Sun Oct 22 00:38:57 2000), transfer sender: Bury (decadent burial), letter area: Programming Title: Fourier Transform Source Sequence Send Station: Yi Xian Tempoken Yat-Sen Channel (Wed Apr 19 13:30:18 2000), station letter sender: PINACLE (ELTON ), The believer: Programming Title: Re: Who has the original way of Fourier transform! urgent need! ! ! ! Sending station: BBS Shuimu Tsinghua Station (Thu Jul 22 10:10:28 1999) #include

#include

#include

#include

#include

Void Initial (int Num_Data, Float * Real, Float * InM);

Void Enter_Data (int Num_Data, Float * Data); Void Wave_sin (int Num_Data, Float * Data);

Void Wave_cos (int Num_Data, Float * Data);

Void Decay (int Num_Data, Float * DATA);

Void Random (int Num_Data, Float * Data);

Void Table (int Num_Data, Char Flag,

FLOAT * TABLESIN, FLOAT * TABLOS;

Void DFT (int Num_Data, Char Flag, Float * Real, Float * IMG,

FLOAT * TABLESIN, FLOAT * TABLOS;

Float period;

void main ()

{

INT NUM_DATA;

INT I;

Char flag;

FLOAT * REAL, * IMG;

Float * Tablecos, * tablesin

Printf ("" ""): ")

Scanf ("% f", & period;

PRINTF ("Please Input Sample Point Number:");

Scanf ("% d", & num_data);

Fflush (stdin);

Printf ("DFT OR IDFT (D / I):");

Flag = getchar ();

IF (flag == 'd') Flag = 'd';

IF (Flag == 'I') Flag = 'I';

Printf ("/ n");

Real = (float *) malloc (sizeof (float) * num_data;

IMG = (float *) malloc (sizeof (float) * num_data;

Tablesin = (float *) malloc (sizeof (float) * num_data;

Tablecos = (float *) malloc (sizeof (float) * num_data;

Initial (NUM_DATA, REAL, IMG);

Table (NUM_DATA, FLAG, TABLESIN, TABLECOS);

DFT (Num_Data, Flag, Real, IMG, Tablesin, TableCOS);

For (i = 0; i

Printf ("% 8D REAL =% 12.6F IMG =% 12.6F / N",

I, REAL [I], IMG [I]);

FRE (REAL);

Free (IMG);

Free (tablesin);

Free (TableCOS);

}

Void Initial (int Num_Data, Float * Real, Float * IMG)

{

Int n;

For (n = 0; N

{

Real [n] = 0;

IMG [N] = 0;

}

Printf ("INITIAL REAL DATA / N");

ENTER_DATA (NUM_DATA, REAL);

Printf ("/ Ninitial Img Data / N");

ENTER_DATA (NUM_DATA, IMG);

}

Void Enter_Data (int Num_Data, Float * Data)

{

Int selection;

Printf ("Function Selection / N");

Printf ("1 ----- Amplitude * SIN (2 * 3.1415926 * frequency * period * t) / n");

Printf ("2 ----- amplitude * cos (2 * 3.1415926

* Frequency * period * t) / n ");

Printf ("3 ----- Amplitude * Exp (-period) / N");

Printf ("4 ---- DATA = 0 / N");

Printf ("5 ----- Enter Data / N);

Printf ("Enter Selection ---");

Scanf ("% D", & selection;

Switch (Selection)

{

Case 1: Wave_sin (NUM_DATA, DATA); BREAK;

Case 2: Wave_cos (NUM_DATA, DATA); BREAK;

Case 3: Decay (Num_Data, DATA); BREAK;

Case 4: Break;

Case 5: Random (NUM_DATA, DATA); BREAK;

}

}

Void Wave_sin (int Num_Data, Float * Data)

{

Float Amplitude, Frequency, C;

Int n;

Printf ("Please Input amplitude of Wave: / N");

Scanf ("% f", & liTude);

Printf ("" "" ": / n");

Scanf ("% f", & frequency);

For (n = 0; N

{

C = 2 * 3.1415926 * frequency * period * n;

Amplitude * sin (c));

}

}

Void Wave_cos (int Num_Data, Float * Data)

{

Float Amplitude, Frequency, C;

Int n;

Printf ("Please Input amplitude of Wave: / N");

Scanf ("% f", & liTude);

Printf ("" "" ": / n");

Scanf ("% f", & frequency);

For (n = 0; N

{

C = 2 * 3.1415926 * frequency * period * n;

Data [n] = (float) (Amplitude * COS (C));

}

}

Void Decay (int Num_Data, Float * DATA)

{

Float Amplitude, C;

Int n;

Printf ("please input amplitude of wave / n");

Scanf ("% f", & liTude);

For (n = 0; N

{

C = -period * n;

Data [n] = (float) (Amplitude * Exp (C));

}

}

Void Random (int Num_Data, Float * DATA)

{

Int n;

For (n = 0; N

{

Printf ("" please input data [% d]: ", n);

Scanf ("% f", & data [n]);

}

}

Void Table (int Num_Data, Char Flag,

FLOAT * TABLESIN, FLOAT * TABLOS {

Float W, C;

Int n;

W = (float) (8 * Atan (1) / Num_DATA);

IF (flag == 'd') w = -w;

For (n = 0; N

{

C = W * n;

Tablecos [N] = (float) COS (C);

Tablesin [N] = (float) sin (c);

}

}

Void DFT (int Num_Data, Char flag, float * img,

Float * Tablesin, Float * Tablecos

{

INT I, J, L;

Float * result_r, * result_i;

Result_r = (float *) malloc (sizeof (float) * num_data;

Result_i = (float *) malloc (sizeof (float) * num_data;

For (i = 0; i

{

Result_r [i] = 0;

Result_i [i] = 0;

For (j = 0; J

{

L = i * j% num_data;

Result_r [i] = result_r [i] real [j] * TableCOS [L]

IMG [J] * Tablesin [l];

Result_i [i] = result_i [i] img [j] * TableCOS [L]

-real [j] * Tablesin [l];

}

}

IF (Flag == 'D')

{

For (i = 0; i

{

Real [i] = result_r [i];

IMG [i] = result_i [i];

}

}

Else IF (flag == 'i')

{

For (i = 0; i

{

REAL [I] = result_r [i] / num_data;

IMG [I] = result_i [i] / num_data;

}

}

Free (Result_r);

Free (result_i);

}

-

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:21:01 [Reply]

On the 14th floor

Sender: Windring (DLL), the letter area: programing Title: Re: ask for five son chess algorithms, how to count more play! Sending station: BBS Shuimu Tsinghua Station (Fri Dec 14 09:34:13 2001) The following is the design idea of ​​black and white chess, and the five sons have more complicated, but similar thinking is easy to design ideas: the current state of the chessboard. Arrive at the Finance Status Calculation Status, and return to the current state to seek most favorable steps (one sub-node of partial returns). Terminology: Pixabay of Chess Computer Square: One. The Opening Status 1. The Chess Bureau has ended 2. The current color has nowhere to be down 3. The depth of the Bo Tree has arrived in the designated depth. Priority Method Saves memory usage during construction, the construction process uses the stack space storage sub-node, the branches that have been completed can be abandoned to save memory (using recursive procedures). The algorithm is simple to describe the following: If the current chess game is the final state, the return state is divided from the state of the current chess game, finding a walking point, trying to drive away this, the new state extension is a child of the current chess game. Node as a new current state recursive call (α-β reduction can be added during this process) Reflections: If the loop replaces recursive, save all constructed nodes, the node of this constructed may be reused when the next constructed tree , Save constructive time. II. Α-β cutting 1.α cut in consideration of a child of chess and a child to play chess, if the numerical value of the child is less than or equal to its affiliate The returns, then do more processing of the node or its subsequent nodes. The calculated process can be returned directly to the affiliate point. 2. β Cutting In consideration of a child of the opponent's play chess and a child of the player chess, if the part of the sub-node has been more than or equal to the partial returns of their affinity points, then There is no need to do more for the child or its posterior node. The calculation process can be returned directly to the pro-native point.

IV. The status of the chess Bureau This function is quantified by the quantization of the number of chess pieces in a state of the chess bureau, and the correct analysis of the chess game is directly related to the high and low considering of the computer chess. The rules of the chess are the tuning speed. Which of the chess pieces on the chessboard wins, the simple status valuation method is a status of the number of chess pieces in a state, but many chess pieces on the board may be eaten by the other party, so better ways It is calculated that all the chess pieces that cannot be eaten by the other party are made as a status. Whether the chess board can be eaten by the other party to the four directions of other chess grids, four directions are: left to upper right The slash (BD_AX) is on the right upper right (fd_ax) horizontal direction (h_ax) horizontal direction (h_ax) vertical direction (v_ax) If it is protected in these four directions, we think that this chess can not be eaten by the other party, one Does the chess pieces are protected in a certain direction, and can be judged by the following method: When the following two cases appear, we can think that this chess is protected in this direction 1. This direction is associated with this pair The chess pieces have arrived between the border 2. This direction is associated with this piece of chess, there is no space (each other pieces, or boundary), and the chess pieces on the four corners must be an unable to eat when the board is empty. Score method: 1. Can't be eaten chess pieces quarter 2. Three direction protected chess pieces three points 3. Two directed chess pieces two points 4. One direction is protected The chess piezetter is seen as a dangerous state when it appears because the importance of the angle is seen, and there will be a placed chess piece on the edge of the reduction, but it is not protected in the direction of the angle. Structure: Each chess body is used by one byte, low two-digit recording piece color, and the high four digits are recorded in four directions. If a chess is empty, the corresponding byte is 0x0, for Avoid border check, add one box around the chessboard, the border corresponds to 0xff ................................................. To:]: I want to push five steps after I hope, but the feedback time requires less than twenty seconds. How can I make a quick abandon: some possibility, thus achieving this effect - 怀 逸 兴 飞 飞 上 上 青 青 上 上This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:25:38 [Reply]

On the 15th floor

Sender: Raphaelzl (Little Flying Bear ~ Stupid), Write Area: Programming Title: Re: Where can I get a C language CRC algorithm to send a letter: BBS Shuimu Tsinghua Station (Tue Apr 17 10:42:25 2001) #include

#include

#define in_file ".//crc.in"

#define max_in_file_size 8192

#define min_in_file_size 1024

Word CRC (Unsigned Char * Info, DWORD LEN)

{

Word ACC;

UNSIGNED Char i;

ACC = 0;

While (len -) {

ACC = ACC ^ ((unsigned int)) << 8);

INFO ;

For (i = 8; i> 0; I -)

IF (ACC & 0x8000) ACC = (ACC << 1) ^ 0x1021;

ELSE ACC << = 1;

}

Return ACC;

}

void main ()

{

Handle Hfile = INVALID_HANDLE_VALUE;

CHAR Ch_IN [MAX_IN_FILE_SIZE];

DWORD DWRW;

Word result; hfile = createfile (in_file, generic_read, 0,

NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL

IF (HFile == Invalid_Handle_Value) {

Printf ("LastError:% D / N", getLastError ());

Exit (1);

}

IF (GetFileSize (HFile, Null)> max_in_file_size ||

GetFileSize (HFILE, NULL)

Printf ("FileSize>% D or FileSize <% D",

Max_in_file_size, min_in_file_size;

CloseHandle (HFILE);

Exit (1);

}

Readfile (HFile, Ch_in, Max_in_File_size, & DWRW, NULL);

CloseHandle (HFILE);

Result = CRC (CH_IN, DWRW);

Printf ("THE CRC CODE IS:% X / N", RESULT);

}

One of CRC32

[In the Lightlk (the most lazy) masterpiece:]

: RT

-

☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★

I really want to pat the little wings.

Fly on the sunny sky.

☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:27:29 [Reply]

On the 16th floor

Sender: Raphaelzl (Little Flying Bear ~ Stupid), Write Area: Programming Title: Re: Where can I get a C language CRC algorithm to send a letter: BBS Shuimu Tsinghua Station (Tue Apr 17 10:42:25 2001) #include

#include

#define in_file ".//crc.in"

#define max_in_file_size 8192

#define min_in_file_size 1024

Word CRC (Unsigned Char * Info, DWORD LEN)

{

Word ACC;

UNSIGNED Char i;

ACC = 0;

While (len -) {

ACC = ACC ^ ((unsigned int)) << 8);

INFO ;

For (i = 8; i> 0; I -)

IF (ACC & 0x8000) ACC = (ACC << 1) ^ 0x1021;

ELSE ACC << = 1;

}

Return ACC;

}

void main ()

{

Handle Hfile = INVALID_HANDLE_VALUE;

CHAR Ch_IN [MAX_IN_FILE_SIZE];

DWORD DWRW;

Word result;

Hfile = Createfile (in_file, generic_read, 0,

NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL

IF (HFile == Invalid_Handle_Value) {

Printf ("LastError:% D / N", getLastError ());

Exit (1);

}

IF (GetFileSize (HFILE, NULL)> Max_in_file_size || getFileSize (HFile, NULL)

Printf ("FileSize>% D or FileSize <% D",

Max_in_file_size, min_in_file_size;

CloseHandle (HFILE);

Exit (1);

}

Readfile (HFile, Ch_in, Max_in_File_size, & DWRW, NULL);

CloseHandle (HFILE);

Result = CRC (CH_IN, DWRW);

Printf ("THE CRC CODE IS:% X / N", RESULT);

}

One of CRC32

[In the Lightlk (the most lazy) masterpiece:]

: RT

-

☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★

I really want to pat the little wings.

Fly on the sunny sky.

☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★ ☆ ★

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:28:16 [Reply]

On the 17th floor

Sender: Marslv (Dream Life), Letter Area: Program Title: Crack Windows Screen Protection Password (Turn) Send Station: BBS Shantou University Tulip Station (Sat Oct 21 23:59:25 2000), transfer sender: Woodmen (never abuse English), letter area: Programming Title: Crack Windows Screen Protection Password Send Station: Yi Xian Tempoken Yat-Sen Channel (Fri Oct 20 20:10:04 2000), station letter [The following is from Peking University One day, I suddenly found that the password you entered cannot be accessed. I know that my forget is committed, so I will sit down and memorize the clue ... I only remember that the same password is used for the Internet and the screen saver. . So find out the big-lamination information, intend to crack the screen protection password! Everyone knows that the screen protection password is up to 16 characters. Microsoft built a 16-byte key: 48 EE 76 1D 67 69 A1 1B 7A 8C 47 F8 54 95 97 5F. Windows encrypts your password you entered with the above key. Its encryption process is: First convert the password characters you entered into its 16-based ASC II code value (lowercase letters first turn to uppercase letters), and then take the corresponding key to the corresponding key, put the resulting 16 When each bit of the value is as a character, convert it to its 16 credit ASCII code, plus 00 as the end flag, deposits into the registry hkey_current_user / control panel / desktop's binary-screen SCREENSAVE_DATA. After understanding its encryption principle, it is not difficult to program the crack my screen protection password (ie the online password). I used VB6.0 to read the function of the Scrrensave_Data value in the registry, and read its value of 31 43 41 33 33 43 35 35 33 34 32 31 00, removed the end sign 00, The remaining byte is converted to the corresponding ASCII character, and each two characters are formed into a 16-grade number: 1C A3 3C 55 34 21, obviously, the password is 6 bits, which will be partially different from the top 6 byte key I got a password ASCII code (16 entered value): 54 4D 4A 48 53 48, the corresponding password is clearly TMJHSH, the crack is successful! Try it with it, huh, immediately came to MODEM cheerful voice.

With the VB source: (using the form for form1, text box text1, command button Command1) 1, Form code: Option ExpliCit Dim Cryptograph As String Dim i AS Integer DIM CRYPTOGRAPHSTR (32 ) As Integer Dim PWstr As String Dim PassWord As String Private Sub Command1_Click () PWstr = "" PassWord = "" Text1.Text = "" Cryptograph = GetBinaryValue ( "ScreenSave_Data") k = Len (Cryptograph) For j = 1 To k - 1 for i = 32 to 126 for i = 32 to 126 if Mid (Cryptograph, J, 1) = CHR (i) THEN CRYPTOGRAPHSTR (j) = I end if Next I next J i = (k - 1) / 2 The 'password number is (h-1) / 2, select the decryption process according to the number of digits.

SELECT CASE I Case 16 GOTO 16 CASE 15 GOTO 15 CASE 14 Goto 14 Case 13 Goto 13 Case 12 Goto 12 Case 11 Goto 11 Case 10 Goto 10 Goto 10 Case 9 Goto 9 Case 8 Goto 8 Case 7 Goto 7 Case 6 Goto 6 case 5 goto 5 case 4 goto 4 case 3 goto 3 case 2 goto 2 case 1 goto 1 Case Else End SELECT 16: PWSTR = PWSTR & CHR (("& H" & chr (Cryptographstr (31)) & chr (Cryptographstr (32 ))) XOR & H5F) 15: PWSTR = Pwstr & Chr ("& H" & chr (Cryptographstr (29)) & chr (Cryptographstr (30))) XOR & H97) 14: Pwstr = Pwstr & Chr (("& H" & Chr (Cryptographstr (27)) & chr (Cryptographstr (28))) XOR & H95) 13: PWSTR = Pwstr & Chr (("& H" & chr (Cryptographstr (25)) & chr (Cryptographstr (26))) XOR & H54) 12: Pwstr = Pwstr & CHR (("& H" & chr (Cryptographstr (23)) & chr (Cryptographstr (24))) XOR & HF8) 11: Pwstr = Pwstr & Chr (("& H" & chr (Cryptographstr) (21)) & chr (Cryptographstr (22)))) XOR & H47) 10: Pwstr = Pwstr & Chr (("& H" & chr (Cryptographstr (19 ))) & Chr (20)))) XOR & H8C) 9: PWSTR = Pwstr & Chr (("& H" & chr (Cryptographstr (17)) & chr (Cryptographstr (18))) XOR & H7A) 8: Pwstr = PWSTR & CHR (("& H" & chr (Cryptographstr (15)) & chr (Cryptographstr (16)))) XOR & H1B) 7: Pwstr = Pwstr & Chr (("& H" & chr (Cryptographstr (13)) & chr (Cryptographstr (14))) xor &

HA1) 6: Pwstr = Pwstr & Chr (("& H" & chr (Cryptographstr (11)) & chr (cryptographstr (12))) XOR & H69) 5: Pwstr = Pwstr & Chr (("& H" & chr (Cryptographstr) (9)) & 5: pwstr = pwstr & chr ("& H" & chr (Cryptographstr (9)) & chr (Cryptographstr (10))) XOR & H67) 4: Pwstr = Pwstr & Chr (("& H" & CHR (Cryptographstr (7)) & chr (Cryptographstr (8))) XOR & H1D) 3: Pwstr = Pwstr & CHR (("& H" & chr (Cryptographstr (5)) & chr (Cryptographstr (6))) xor & H76 2: pwstr = pwstr & chr ("& H" & chr (Cryptographstr (3)) & chr (Cryptographstr (4))) XOR & Hee) 1: Pwstr = Pwstr & Chr (("& H" & chr (Cryptographstr 1))) & chr (Cryptographstr (2))) XOR & H48) for i = i to 1 step -1 'The value of the PWSTR is the password inverted sequence, and the password is derived. Password = Password & Mid (PWSTR , i, 1) Next I TEXT1.TEXT = password 'Displays the password in the text box.

End Sub 2, module code: Option Explicit Const ERROR_SUCCESS = 0 & Const ERROR_BADDB = 1009 & Const ERROR_BADKEY = 1010 & Const REG_EXPAND_SZ = 2 & Const REG_BINARY = 3 & Const KEY_QUERY_VALUE = & H1 & Const KEY_ENUMERATE_SUB_KEYS = & H8 & Const KEY_NOTIFY = & H10 & Const READ_CONTROL = & H20000 Const STANDARD_RIGHTS_READ = READ_CONTROL Const KEY_READ = STANDARD_RIGHTS_READ Or KEY_QUERY_VALUE Or KEY_ENUMERATE_SUB_KEYS Or KEY_NOTIFY Const HKEY_CURRENT_USER = & H80000001 Dim hKey As Long, MainKeyHandle As Long Dim rtn As Long, lBuffer As Long, sBuffer As String, SubKey As String Dim lBufferSize As Long Declare Function RegOpenKeyEx Lib "advapi32.dll" Alias ​​"RegOpenKeyExA" (ByVal hKey As Long, ByVal lpSubKey As String, ByVal ulOptions As Long, ByVal samDesired As Long, phkResult As Long) As Long Declare Function RegCloseKey Lib "advapi32.dll" (ByVal hKey As Long) As Long Declare Function Regqueryvalueex lib "advapi32.dll" Alias ​​"REG QueryValueexa" (ByVal HKEY As Long, BYV al lpValueName As String, ByVal lpReserved As Long, lpType As Long, ByVal lpData As String, lpcbData lpData As String, lpcbData As Long) As Long Function GetBinaryValue (Entry As String) MainKeyHandle = HKEY_CURRENT_USER SubKey = "Control Panel / desktop /" rtn = RegOpenKeyEx (MainKeyHandle, SubKey, 0, KEY_READ, hKey) If rtn = ERROR_SUCCESS Then 'if HKEY_CURRENT_USER / Control Panel / desktop key is successfully opened lBufferSize = 1 rtn = RegQueryValueEx (hKey, Entry, 0, REG_BINARY, 0, lBufferSize)' Read Screensave_Data's value sbuffer =

Space (lBufferSize) rtn = RegQueryValueEx (hKey, Entry, 0, REG_BINARY, sBuffer, lBufferSize) If rtn = ERROR_SUCCESS Then 'ScreenSave_Data read value if successful rtn = RegCloseKey (hKey) GetBinaryValue = sBuffer' function returns the value ScreenSave_Data Else ' If the read value ScreenSave_Data unsuccessful call ErrorMsg End End If Else 'if HKEY_CURRENT_USER / Control Panel / desktop key can not open the call ErrorMsg' call ErrorMsg () procedure call ErrorMsg 'call ErrorMsg () process End End If End Function Private Sub ErrorMsg ( ) 'Display error message SELECT CASE RTN CASE ERROR_BADDB MSGBOX ("Your computer registry has an error!") Case error_badkey, reg_expand_sz msgbox ("Your computer does not have a screen security code!") Case Else Msgbox ("Crack process To an unknown error, error number: "& STR $ (RTN)) End select end sub -.. - ~ / /` - '/.' `-: | /` ._ | |. - '`. 怀 兴 兴 壮 飞 上 青 青 青 青 揽 明 明 明 明 此 此 此 此 明 明 明

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:29:39 [Reply]

On the 18th floor

Vibrating password algorithm BREATH // ************************************************************ *********************** // In many cases we need exhaustion algorithms, such as password dictionary. // The key to this algorithm is the issue of password subscript. In //, the write file statement in this example is relatively low, and it is not optimized to reduce algorithm complexity. // If you want to improve the efficiency of your write file, you can use the buffer to write in batches. //***************************************************** BREATH.CNPICK .com ***** void createpassword () {#define passwordmax 8 // The maximum length of the password will generate the maximum length of CHAR A [] = "0123456789abcdefghijklmnopqrStuvwxyz"; // Possible character Long ndictcount = sizeof (a); // Get password Dictionary length char CPASS [PasswordMax 2]; // will generate the password long nminl = 1, nmaxl = 3; // This example is from 1-3long array [passwordmax]; // password dictionary subscript (nminl <= nmaxl && nmaxl <= passwordmax); // Fault tolerance guarantees long NLENGTH = NMINL; Register Long J, i = 0; Bool BNext; cstdiofile File; File.Open ("C: //Dict.txt", CFile :: Modecreate | CFILE :: ModeWrite; While (NLENGTH <= nmaxl) {for (i = 0; IARRAY [i] = 0;

Bnext = True;

While (BNEXT)

{

For (i = 0; i

CPASS [I] = a [Array [i]];

CPASS [I] = '/ 0';

File.writeString (CPASS);

File.writestring ("/ n");

For (j = NLENGTH-1; J> = 0; J -) // password pointer carry

{

Array [J] ;

IF (Array [J]! = NDictCount-1) Break;

Else

{

Array [J] = 0;

IF (j == 0) bnext = false;

}

}

}

NLENGTH ;

}

File.Close ();

}

Allowed to fly

Want to take Qingtian Mingyue

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:34:04 [Reply]

Section 19th floor

Sender: MARSLV (Fantasy Life), Letter Area: Program Title: Life Law (Transfer) Send Restaurant: BBS Shantou University Tulip Station (Sun Oct 22 09:16:08 2000), transfer sender: Messages.bbs @ bbs.whu.edu.cn (Youth Heart), Letter: DOS Title: Life Law Send Station: Lushan Water (Sat May 22 19:05:50 1999) Transmission Station: Argo! News.zsu. edu.cn! WHUNEWS! WHUBBS Sender: Vinc (Never Mind), Letter Area: DOS Title: Life Law Send Station: Sakura Castle (Sat May 22 17:22:38 1999), transfer This is a very famous John Comway's life law proposition, his best is: in a space, the group with a certain shape of the living body is in the interest, their life law is: 1. If there are more than three life around a living body There is existence, it will die because it is too crowded; 2. If there is less than two living things around a living body, it will die because of loneliness; 3. If there is no life in a space, but around it There are two or three living life, and the new life will be generated on this space. People who have learned the computer algorithm must not be unfamiliar with this proposition? The program I use the assembly language can be made as described above (I have never seen the compilation language to compile this program ... Faint ... Is the assembly language is too difficult? Too hardware? I feel used The assembly language is really cool! Moreover, I don't have the algorithm used by the Pascal routine in the general textbook, and the Pascal routine on the book uses two buffers to store life. Location and processing intermediate results, I only used a buffer ... um ... it is really cool ... just the interface is a bit simple, this is the advantage of other advanced languages ​​...), the main function key is First move the left and right direction keys and the Enter key to place the position of the first generation of life, and then enter the carriage return. Then the program starts calculating the destiny of the descendant. Each one can be calculated once, press the ESC button to restart the program, press the Q key to exit.

Life.asm Code Segment Assume CS: CS: CODE, DS: Code, ES: CODE, SS: CODE ORG 100H Start: Jmp Main Version DB "Bruce's Law of Life Version 1.00", 0 GAP DB 'Generation 00', 07,00 BUFF DB 20 * 20 DUP (?) Count DB 0 Total DW 0 ROW DB 0 COL DB 0 DISP: MOV AH, 0EH MOV BL, 0FH INT 10H RET CLS: MOV AX, 0700H MOV BH, 0FH MOV CX, 0 MOV DX , 184FH INT 10h Ret Down: MOV Al, 08H Call Disp Mov Al, 0AH Call DISP MOV Al, 'JMP DISP LINE: MOV CX, 14H LOP1: MOV Al,' Call Disp loop Lop1 Ret Downline: MOV CX, 14H LOP2: CALL DOWN LOOP LOP2 RET SETPOSITION: MOV AH, 02H MOV BH, 00H INT 10h Ret Echo: Lodsb or Al, Al Jz Return Call Disp Jmp Echo Return: Ret Turn: MOV DX, 0A03H CALL SetPosition Inc Byte PTR [GAP] [0DH] CMP BYTE PTR [GAP] [0DH], '9' JBE OK MOV BYTE PTR [GAP] [0DH], '0' Inc Byte PTR [GAP] [0ch] OK: MOV SI, OFFSET GAP CALL Echo Ret Chess: Mov Ah, 0EH MOV BL, 0FH MOV Al, '*'

INT 10h Call Back Ret Back: MOV DL, [Col] MOV DH, [ROW] Call SetPosition Call getPosition Ret Compchar: Call Readchar Cmp Al, '*' Jnz Return1 Inc Count Return1: Ret GetPosition: MOV AH, 03H MOV BH, 00h INT 10H MOV [Col], DL MOV [Row], DH Ret Readchar: MOV AH, 08H MOV BH, 00H INT 10H RET Receive: MOV DX, 0433H Call setPosition Call getPosition Mov Di, Offset Buff Mov Word Ptr [Total] 0 LOPR: CALL COMPARE CALL GETPSITION INC DL CMP DL, 46H JBE SETR MOV DL, 33H INC DH; CMP DH, 17H; JBE SETR RET SETR:; XOR ax, AX;

INT 16H CALL SETPSITION CALL GETPosition Inc Word PTR [Total] CMP Word PTR [Total], 20 * 20 JB LOPR RET TEST1: CALL SetPosition Call Compchar Call Back Ret Compare: Mov Count, 0 Call GetPosition Inc DH CALL TEST1 DEC DH CALL TEST1 INC DL CALL TEST1 DEC DL CALL TEST1 INC DH INC DL CALL TEST1 INC DH DL CALL TEST1 DH INC DL CALL TEST1 DEC DH INC DL CALL TEST1 DEC DH DL CALL TEST1 CALL READCHAR CMP Al, '*' JZ Have Cmp Count, 3 JZ Point Blank: Mov Al, 20H Stosb Ret Have: CMP Count, 3 Ja Blank Cmp Count, 2 JB Blank Point: MOV Al, '*'

Stosb Ret Putpicture: MOV DX, 0433H CALL SETPSITION CALL GETPSITION MOV SI, OFFSET BUFF MOV WORD PTR [TOTAL], 0 LOPP: CALL GETPSITION CMP DL, 46H JBE SETP MOV DL, 33H INC DH Setp: Call SetPosition Inc Word PTR [Total ] Lodsb Call Disp CMP Word Ptr [Total], 20 * 20 JB Lopp Ret Main: Call CLS MOV CX, 20 * 20 MOV DI, Offset Buff Mov Al, 0 Rep Stosb Mov Word PTR [GAP] [0ch], 3030H MOV DX, 0228H Call SetPosition Mov Si, Offset Version Call Echo Mov DX, 0332H Call setPosition MOV Al, '? Call Disp Call Line MOV Al, '? Call DISP CALL DOWNLINE MOV DX, 0333H CALL SETPSITION CALL DOWNLINE MOV AL, 08H CALL DISP MOV AL, 0AH CALL DISP MOV AL,'? Call Disp Call Line Mov Al, '?

call disp call turn mov dx, 0e3dh direct: call setposition call getposition getkey: xor ax, ax int 16h cmp ax, 011bh jz main cmp ax, 4800h jnz dir_down cmp byte ptr [row], 4 jz getkey dec dh jmp direct dir_down: cmp ax, 5000h jnz dir_left cmp byte ptr [row], 17h jz getkey inc dh jmp direct dir_left: cmp ax, 4b00h jnz dir_right cmp byte ptr [col], 33h jz getkey dec dl jmp direct dir_right: cmp ax, 4d00h jnz enter1 CMP BYTE PTR [Col], 46h JZ Getkey Inc DL JMP Direct EXIT: CALL CLS MOV DX, 0 CALL SETPOS ition mov ax, 4c00h int 21h enter1: cmp al, 0dh jz confirmed jmp getkey confirmed: call readchar cmp al, 20h jnz confirm_again call chess no: jmp getkey confirm_again: xor ax, ax int 16h cmp al, 0dh jnz no start_cal: call Turn Call Receive Call Putpicture XOR AX, AX INT 16H CMP AH, 01H JNZ Continue Jmp Main Continue: CMP AH, 10H jz endcode jmp start_cal endcode:

JMP EXIT code Ends End Start -.. - ~ / / `- '/.' -: | /`. - '`. 怀 兴 飞 飞 上Qingtian City Moon This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:38:56 [Reply]

20th floor

Sender: Allanli (Dust), Word Area: Program Title: Realize Up and Down Jump Trigger. Sending Station: BBS Shantou University Tulip Station (WED MAY 3 16:14:18 2000), transfer the following procedure is a PIC16CXX series A piece of code for the single-chip assembly language, the function is delayed, because some reason cannot be implemented in a space loop, I don't know if there is any better way? Also the counting block implementation only counts the pulse rising edge, is it still Have a better way?; ----------------------------------------- -------------------------------; ***************** ****************; * This function is used to initialize the register *; * *; * see: function isconfirm1 *; * Return value: nothing *; *************************************************** CLSCONFIRM1 CLRF 0xC CLRF 0xD RetLW 0x0; End of Clsconfirm1; --------------------------------------- ------------------------------------------------ -; *******************************; * This function is used Whether the monitor button is pressed 20ms *; * When calling clsconfirm1, it starts to calculate 0 seconds *; * *; * See: Function clsconfirm1 *; * Return value: If more than 20 ms seconds return 0xFF *; * Otherwise returns 0x0 *; ** ********************************************************* ISCONFIRM1 MOVF Portc, W; Portc-> W, retain portc status to W andLW 0x80; W's highest bit preserved the output value of the zero-zero comparator xorwf 0xc, W; W; W. The value is compared to the value retained in the FC, affecting Z Bit. BTFSC 0x3, 0x2; Judging whether the state memory Z bit is zero, it is zero W <> Fc, that is, zero. RetLW 0x0; Z bit is not zero, that is, W = Fc, no zero, return xorwf 0xc; if zero, ie, the transitioner is too zero, save the status of Portc (7) to the FC.

BTFSC 0x3, 0x2; Judgment Status Memor Z bit is zero RetLW 0x0; W = fc, this cross zero is a negative hop, not count, return to INCF 0xD; cross zero, this zero is positive hop, count, FD increases 1 MOVLW 0x2; SubWF 0xD, W; Judgment FD is> = 2h, if the determination key is still pressed by BTFSS 0x3, 0x0; detect the C bit RetLW 0x0; C bit is 0, borrow, FD <2h Returns 0x0 MOVLW 0x2; C bit is 1, no borrow, fd> = 2h MOVWF 0xD; 2H-> fd, keep fd> = 2h MOVF portb, W; judgment key still presses MOVWF 0x1f; BTFSC 0x1f, 0x2 The state of detecting RB2, that is, if there is a key to press RETLW 0xFF; the key is still pressed, return 0xff RetLW 0x0; key has been released, return 0x0; end of isconfirm1 - Since it is destined to wander, why should he be pushed? difficult. E-mail: Allan_stu@163.net If you want to be on the beach, why should the sea will block everywhere.逸 逸 兴 飞 飞 青 青 天 揽 明 明 明 明 此 此 明 此 明 明 此 明 明

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:43:21 [Reply]

On the 21st floor

Allowingly, we want to take the sky, the moon

This post has not been scored

Author: lanjingquan expert points: 500

Member information Short message email

Published: 2003-10-3 23:44:49 [Reply]

No. 22

It's so much, and some other have not been returned before. Allowingly, we want to take the sky, the moon

This post has not been scored

Website Profile - Website Navigation - Advertising Service - invites to join - Contact webmaster - friendship link CopyRight © 1999-2004 Programfan.com. All Rights Reserved Forum Making & Maintenance: Hannibal QQ: 15987743