回 帖 发 新 帖 刷新版面

主题:我见到过的一些常用算法

在网上看到的一些东西,贴出来供大家参考.

回复列表 (共31个回复)

沙发

发信人: Marslv (梦幻人生), 信区: Program
标  题: 算法--黑白棋子(转)
发信站: BBS汕头大学郁金香站 (Sat Oct 21 23:57:24 2000), 转信
发信人: jek (好好学习天天向上), 信区: Program
标  题: 黑白棋子
发信站: BBS 荔园晨风站 (Sat Mar 11 14:50:46 2000), 转信
//黑白棋子
#include <iostream.h>
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<<c[i];
cout<<endl;
}
--
            .      .-~\
           / `-'\.'    `- :
           |    /          `._
           |   |   .-.        {
            \  |   `-'         `.

板凳

发信人: LaoHong (批处理中), 信区: Program
标  题: 计算24点的程序
发信站: BBS汕头大学郁金香站 (Sun Sep  9 18:30:55 2001), 转信
看大家一直在孜孜以求的计算24, 不如贴个程序出来,
可以在1秒种之内解决任何计算24的问题. 当然想算25, 26...
也是可以的. 希望以此作为24问题的终结.
#include "stdafx.h"
//
//原理, 将4个数字和3个运算符按"波兰表达式"组成一个序列,
// 计算该序列的值是否为所求目标. 可以对这个序列的组成
// 进行遍历, 以确定是否有解.
//根据我的计算如果只限于用1-10之间的数字计算24, 总共有
// 715个不同的题目, 其中566个有解. 如果是1-13, 则有
// 1820个不同的题目, 其中1362个有解
//
int total = 0; //解的个数
int sp; //当前表达式栈指针
int s[7]; //表达式栈
void Evaluate(int& fz, int& fm)
//计算表达式的值, fz, fm为计算结果的分子, 分母
{
int op, l, m, opn[4];
op = s[sp]; //取栈顶元素
for (l = 0; l < 4; l += 2)
{
if ((m = s[++sp]) > 0) //是数字
{
opn[l] = m;
opn[l + 1] = 1;
}
else //是运算符
Evaluate(opn[l], opn[l + 1]);
}
//根据运算符进行计算
//opn[0]/opn[1] 是第一个操作数,
//opn[2]/opn[3] 是第二个操作数,
switch (op)
{
case -4: //乘法
fz = opn[0] * opn[2];
fm = opn[1] * opn[3];
break;
case -3: //加法
fz = opn[0] * opn[3] + opn[1] * opn[2];
fm = opn[1] * opn[3];
break;
case -2: //减法
fz = opn[0] * opn[3] - opn[1] * opn[2];
fm = opn[1] * opn[3];
break;
case -1: //除法
fz = opn[0] * opn[3];
fm = opn[1] * opn[2];
break;
}
}
void Display(CString& m)
//将表达式转换为字符串
{
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 - 计算结果(一般为24)
// a, b, c, d - 参加计算的4个数
// ma - 解的字符串表达形式
{
int l1, l2, l3, op1, op2, op3;
int l, fz, fm, num[4];
CString m;
//记录表达式中间四个元素的排列方式
// 其中loc[i][0], loc[i][1]表示第二, 第三两个运算符的位置
// loc[i][2], loc[i][3]表示第一, 第二两个操作数的位置
int loc[5][4] = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3},
{2, 3, 1, 4}, {2, 4, 1, 3}};
//num中记录a, b, c, d的一个排列
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;
//表达式最后两个必须是数字
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++)
{
//表达式第一个必须运算符
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);
//分母不为0, 可以整除, 商为24表示计算成功
if (fm != 0 && fz % fm == 0 && fz / fm == target)
{
Display(m);
ma.Add(m);
total++;
//这里加return就是只求一个解,
//否则是求出全部解(没有考虑剔除重复解)
return;
}
}
}
}
}
}
}
}
}
--

3 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: Huffman算法 (转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:42:31 2000), 转信
发信人: bury (颓废的埋葬), 信区: Programming
标  题: Huffman算法
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 19 13:37:43 2000), 站内信件
发信站: BBS 水木清华站 (Sat Feb 26 23:47:50 2000)
以前写的一个C程序不见了,刚好在华工的站上
有VC的,就顺手贴了过来了,算法流程应该是最
重要的,很多讲数字压缩的都有Huffman算法.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dir.h>
#include <dos.h>
#include <direct.h>
#include <bios.h>
#include <conio.h>
#include <time.h>
#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 < N; 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 < F; 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) < match_po
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)  /* Deleting 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[dad[q]] = lson[q];
                        dad[lson[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(void)        /* 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 - putlen);
                } else {
                        putbuf <<= 8;
                        codesize++;
                }
        }
}
/* initialize freq tree */
void StartHuff()
{
        int i, j;
        for (i = 0; i < N_CHAR; 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 < T; 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 < T; i += 2, j++) {
                k = i + 1;
               f = freq[j] = freq[i] + freq[k];
                for (k = j - 1; f < freq[k]; k--);
                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 < T; 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-ordered */
                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 < T) prnt[i + 1] = l;
                        j = son[l];
                        son[l] = i;
                        prnt[j] = c;
                        if (j < T) prnt[j + 1] = c;
                        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 EncodeEnd()
{
        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 < T) {
                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 (fwrite(&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 < r; i++)
                text_buf[i] = ' ';
        for (len = 0; len < F && (c = getc(infile)) != EOF; 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);
                }
                last_match_length = match_length;
                for (i = 0; i < last_match_length &&
                                (c = getc(infile)) != EOF; i++) {
                        DeleteNode(s);
                        text_buf[s] = c;
                        if (s < F - 1)
                                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++ < last_match_length) {
                        DeleteNode(s);
                        s = (s + 1) & (N - 1);
                        r = (r + 1) & (N - 1);
                        if (--len) InsertNode(r);
                }
        } while (len > 0);
        EncodeEnd();
        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 (fread(&textsize, sizeof textsize, 1, infile) < 1)
                Error("Unable to read");  /* read size of original text */
        if (textsize == 0)
                return;
        StartHuff();
        for (i = 0; i < N - F; i++)
                text_buf[i] = ' ';
        r = N - F;
        for (count = 0; count < textsize; ) {
                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 < j; 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);
}
//解码调用程序
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;
}
--

4 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: Huffman算法 (转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:42:31 2000), 转信
发信人: bury (颓废的埋葬), 信区: Programming
标  题: Huffman算法
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 19 13:37:43 2000), 站内信件
发信站: BBS 水木清华站 (Sat Feb 26 23:47:50 2000)
以前写的一个C程序不见了,刚好在华工的站上
有VC的,就顺手贴了过来了,算法流程应该是最
重要的,很多讲数字压缩的都有Huffman算法.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dir.h>
#include <dos.h>
#include <direct.h>
#include <bios.h>
#include <conio.h>
#include <time.h>
#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 < N; 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 < F; 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) < match_po
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)  /* Deleting 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[dad[q]] = lson[q];
                        dad[lson[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(void)        /* 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 - putlen);
                } else {
                        putbuf <<= 8;
                        codesize++;
                }
        }
}
/* initialize freq tree */
void StartHuff()
{
        int i, j;
        for (i = 0; i < N_CHAR; 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 < T; 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 < T; i += 2, j++) {
                k = i + 1;
               f = freq[j] = freq[i] + freq[k];
                for (k = j - 1; f < freq[k]; k--);
                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 < T; 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-ordered */
                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 < T) prnt[i + 1] = l;
                        j = son[l];
                        son[l] = i;
                        prnt[j] = c;
                        if (j < T) prnt[j + 1] = c;
                        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 EncodeEnd()
{
        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 < T) {
                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 (fwrite(&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 < r; i++)
                text_buf[i] = ' ';
        for (len = 0; len < F && (c = getc(infile)) != EOF; 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);
                }
                last_match_length = match_length;
                for (i = 0; i < last_match_length &&
                                (c = getc(infile)) != EOF; i++) {
                        DeleteNode(s);
                        text_buf[s] = c;
                        if (s < F - 1)
                                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++ < last_match_length) {
                        DeleteNode(s);
                        s = (s + 1) & (N - 1);
                        r = (r + 1) & (N - 1);
                        if (--len) InsertNode(r);
                }
        } while (len > 0);
        EncodeEnd();
        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 (fread(&textsize, sizeof textsize, 1, infile) < 1)
                Error("Unable to read");  /* read size of original text */
        if (textsize == 0)
                return;
        StartHuff();
        for (i = 0; i < N - F; i++)
                text_buf[i] = ' ';
        r = N - F;
        for (count = 0; count < textsize; ) {
                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 < j; 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);
}
//解码调用程序
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;
}
--

5 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: 最小生成树(转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:30:24 2000), 转信
最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图
中选择n-1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树
的权最小。
  为了得到最小生成树,人们设计了很多算法,最著名的有prim算法和kruskal算
法。教材中介绍了prim算法,但是讲得不够详细,理解起来比较困难,为了帮助大家
更好的理解这一算法,本文对书中的内容作了进一步的细化,希望能对大家有所帮助

  假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则
prim算法通过以下步骤可以得到最小生成树:
  1:初始化:U={u 0},TE={}。此步骤设立一个只有结点u 0的结点集U和一个空
的边集TE作为最小生成树的初始行态,在随后的算法执行中,这个行态会不断的发生
变化,直到得到最小生成树为止。
  2:在所有u∈U,v∈V-U的边(u,v)∈E中,找一条权最小的边(u 0,v 0),将此边
加进集合TE中,并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条
边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V-U中,其次
边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的
那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发
生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解
算法时要密切注意。
  3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我
们可以算出当U=V时,步骤2共执行了n-1次(设n为图中顶点的数目),TE中也增加了
n-1条边,这n-1条边就是需要求出的最小生成树的边。
  了解了prim算法的基本思想以后,下面我们就可以看看具体的算法。
  为了和教材保持一致,我们仍然规定:连通网用邻接矩阵net表示,若两个顶点之
间不存在边,其权值为计算机内允许最大值,否则为对应边上的权值。
   首先定义数据类型:
  type adjmatrix=array [1..n,1..n] of real;
  //定义一个n*n的矩阵类型adjmatrix,以便存储邻接矩阵//
  edge=record
     beg,en:1..n;
     length:real;
     end;
  //定义边的存储结构为edge,其中beg是边的起点, en 是边的终点,length是边
的权值//
   treetype=array [1..n-1] of edge;
  //定义一个基类型为edge的数组类型  treetype,其元素个数为n-1个//
  var net:adjmatrix;
  //定义一个adjmatrix类型的变量net,图的邻接矩阵就存放在net中//
  tree:treetype;
  //定义一个treetype类型的变量tree,tree中可以存放n-1条边的信息,包括
起点、终点及权值。在算法结束后,最小生成树的n-1 条边就存放在tree中//
  算法如下(设n为构造的出发点):
  procedure prim(net:adjmatrix;var tree:treetype);
  //过程首部.参数的含义是:值参数net传递图的邻接矩阵,变参tree指明最小生
成树的存放地址//
  begin
 for v:=1 to n-1 do
  //此循环将顶点n与图中其它n-1个顶点形成的n-1条边存放在变量tree中
//
  [tree[v].beg:=n;
  tree[v].en:=v;
  tree[v].length:=net[v]]
  for k:=1 to n-1 do
  //此循环执行算法思想中的步骤2,循环体每执行一次,TE中将增加一条边,在算
法中,这条增加的边存放在变量tree中的第k个元素上,可以这样认为,tree中从第1
到第k号元素中存放了TE和U的信息。注意:在算法思想中我们特别提醒了TE和U的动
态性,表现在算法中,这种动态性 体现在循环变量k的变化上。//
  [min:=tree[k].length;
  for j:=k to n-1 do
   if tree[j].length<min then
     [min:=tree[j].length;
     m:=j;]
   //上面两条语句用于搜索权值最小的边//
  v:=tree[m].en;
  //此语句记录刚加入TE中的边的终点,也即即将加入U中的顶点//
  edge:=tree[m];
  tree[m]:=tree[k];
  tree[k]:=edge;
  //上面三句用于将刚找到的边存储到变量tree的第k号元素上//
  for j:=k+1 to n-1 do
  //此循环用于更新tree中第k+1到第n-1号元素。更新以后这些元素中的en子
项是各不相同的,它们的全部就是集合V-U;beg子项则可以相同,但它们需满足两个
条件:一是应属于集合U;另一是beg子项和en子项行成的边,在所有与顶点en联系的
边中权值应最小。//
  [d:=net[v.tree[j].en];
   if d<tree[j].length
    then [tree[j].length:=d;
       tree[j].beg:=v;]
   ]
  ]
  for j:=1 to n-1 do
  //此循环用于输出最小生成树//
  writeln(tree[j].beg,tree[j].en,tree[j].length);
  end;
  此算法的精妙之处在于对求权值最小的边这一问题的分解(也正是由于这种分
解,而导致了算法理解上的困难)。按照常规的思路,这一问题应该这样解决:分别
从集合V-U和U中取一顶点,从邻接矩阵中找到这两个顶点行成的边的权值,设V-U
中有m个顶点,U中有n个顶点,则需要找到m*n个权值,在这m*n个权值中,再查找权
最小的边。循环每执行一次,这一过程都应重复一次,相对来说计算量比较大。而
本算法则利用了变量tree中第k+1到第n-1号元素来存放到上一循环为止的一些比
较结果,如以第k+1号元素为例,其存放的是集合U中某一顶点到顶点tree.en的边,
这条边是到该点的所有边中权值最小的边,所以,求权最小的边这一问题,通过比较
第k+1号到第n-1号元素的权的大小就可以解决,每次循环只用比较n-k-2次即可
,从而大大减小了计算量。
--
          .  \ |                /
        ~-.`. \|            .-~_
           `.\-.\       .-~      \
             `-'/~~ -.~          /
           .-~/|`-._ /~~-.~ -- ~
          /  |  \    ~- . _\

6 楼


循环冗余校验 CRC的算法分析和程序实现
西南交通大学计算机与通信工程学院  刘东
摘要   通信的目的是要把信息及时可靠地传送给对方,因此要求一个通信系统传输消息必须可靠与快速,在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性,通信系统都采用了差错控制。本文详细介绍了循环冗余校验CRC(Cyclic Redundancy Check)的差错控制原理及其算法实现。

关键字  通信 循环冗余校验  CRC-32  CRC-16  CRC-4

概述
在数字通信系统中可靠与快速往往是一对矛盾。若要求快速,则必然使得每个数据码元所占地时间缩短、波形变窄、能量减少,从而在受到干扰后产生错误地可能性增加,传送信息地可靠性下降。若是要求可靠,则使得传送消息地速率变慢。因此,如何合理地解决可靠性也速度这一对矛盾,是正确设计一个通信系统地关键问题之一。为保证传输过程的正确性,需要对通信过程进行差错控制。差错控制最常用的方法是自动请求重发方式(ARQ)、向前纠错方式(FEC)和混合纠错(HEC)。在传输过程误码率比较低时,用FEC方式比较理想。在传输过程误码率较高时,采用FEC容易出现“乱纠”现象。HEC方式则式ARQ和FEC的结合。在许多数字通信中,广泛采用ARQ方式,此时的差错控制只需要检错功能。实现检错功能的差错控制方法很多,传统的有:奇偶校验、校验和检测、重复码校验、恒比码校验、行列冗余码校验等,这些方法都是增加数据的冗余量,将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验,再将得到的校验码和接受到的校验码比较,如果二者一致则认为传输正确。但这些方法都有各自的缺点,误判的概率比较高。
循环冗余校验CRC(Cyclic Redundancy Check)是由分组线性码的分支而来,其主要应用是二元码组。编码简单且误判概率很低,在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其&nbsp;算法实现。

一、循环冗余校验码(CRC)
CRC校验采用多项式编码方法。被处理的数据块可以看作是一个n阶的二进制多项式,由 。如一个8位二进制数10110101可以表示为: 。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。
采用CRC校验时,发送方和接收方用同一个生成多项式g(x),并且g(x)的首位和最后一位的系数必须为1。CRC的处理方法是:发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。
CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。CCITT建议:2048 kbit/s的PCM基群设备采用CRC-4方案,使用的CRC校验码生成多项式g(x)= 。采用16位CRC校验,可以保证在  bit码元中只含有一位未被检测出的错误 。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16,其生成多项式g(x)= ;而在CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16,其生成多项式g(x)= 。CRC-32的生成多项式g(x)= 。CRC-32出错的概率比CRC-16低 倍 。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。
二、CRC校验码的算法分析
CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下:
设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为 。
用生成多项式g(x)去除 ,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。
用 以模2的方式减去y(x),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。
从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式 ,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时 可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。
为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。
设待发送的数据t(x)为12位的二进制数据100100011100;CRC-4的生成多项式为g(x)= ,阶数r为4,即10011。首先在t(x)的末尾添加4个0构成 ,数据块就成了1001000111000000。然后用g(x)去除 ,不用管商是多少,只需要求得余数y(x)。下表为给出了除法过程。
除数次数 被除数/ g(x)/结果     余数
0  1 001000111000000 100111000000
 1 0011
 0 000100111000000
1  1 00111000000   1000000
 1 0011 
 0 00001000000
2  1 000000 1100
 1 0011
 0 001100

从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述:
//reg是一个5 bits的寄存器
把reg中的值置0.
把原始的数据后添加r个0.
While (数据未处理完)
Begin
If (reg首位是1)
reg = reg XOR 0011.
把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。
End
reg的后四位就是我们所要求的余数。
这种算法简单,容易实现,对任意长度生成多项式的G(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以一次处理8位比较合适。
为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程:
由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0(reg的0位),同时reg3的数据移出reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和g(x)进行XOR运算;移出的数据为0时,reg不与g(x)进行XOR运算,相当与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有 种选择。上述算法可以描述如下,
//reg是一个4 bits的寄存器
初始化t[]={0011,0000}
把reg中的值置0.
把原始的数据后添加r个0.
While (数据未处理完)
Begin
把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。
reg = reg XOR t[移出的位]
End
上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初值为0x00000000,数据依次移入reg0(reg的0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit,所以有 种选择。上述算法可以描述如下:
//reg是一个4 Byte的寄存器
初始化t[]={…}//共有 =256项
把reg中的值置0.
把原始的数据后添加r/8个0字节.
While (数据未处理完)
Begin
把reg中的值左移一个字节,读入一个新的字节并置于reg的第0个byte的位置。
reg = reg XOR t[移出的字节]
End
算法的依据和多项式除法性质有关。如果一个m位的多项式t(x)除以一个r阶的生成多项式g(x), ,将每一位 (0=<k<m)提出来,在后面不足r个0后,单独去除g(x),得到的余式位 。则将 后得到的就是t(x)由生成多项式g(x)得到的余式。对于CRC-32,可以将每个字节在后面补上32个0后与生成多项式进行运算,得到余式和此字节唯一对应,这个余式就是上面算法种t[]中的值,由于一个字节有8位,所以t[]共有 =256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节,通过查表法进行运算,大大提高了处理速度,故为大多数应用所采用。
三、CRC-32的程序实现。
为了提高编码效率,在实际运用中大多采用查表法来完成CRC-32校验,下面是产生CRC-32校验吗的子程序。
unsigned long  crc_32_tab[256]={
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d
};//事先计算出的参数表,共有256项,未全部列出。

unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long  len)
{
unsigned long oldcrc32;
unsigned long crc32;
unsigned long oldcrc;
unsigned  int charcnt;
        char c,t;
oldcrc32 = 0x00000000; //初值为0
    charcnt=0;
while (len--) {
                t= (oldcrc32 >> 24) & 0xFF;   //要移出的字节的值
oldcrc=crc_32_tab[t];         //根据移出的字节的值查表
                c=DataBuf[charcnt];          //新移进来的字节值
                oldcrc32= (oldcrc32 << 8) | c;   //将新移进来的字节值添在寄存器末字节中
                oldcrc32=oldcrc32^oldcrc;     //将寄存器与查出的值进行xor运算
                charcnt++;
}
        crc32=oldcrc32;
        return crc32;
}
参数表可以先在PC机上算出来,也可在程序初始化时完成。下面是用于计算参数表的c语言子程序,在Visual C++ 6.0下编译通过。
#include <stdio.h>
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);
// 交换bit0和bit7,bit1和bit6,类推
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个值
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);
}
}
结束语
    CRC校验由于实现简单,检错能力强,被广泛使用在各种数据校验应用中。占用系统资源少,用软硬件均能实现,是进行数据传输差错检测地一种很好的手段。
参考文献
[1]  王新梅 肖国镇. 纠错码-原理与方法.西安:西安电子科技大学出版社,2001
[2]  罗伟雄 韩力 原东昌 丁志杰 通信原理与电路. 北京:北京理工大学出版社,1999
[3]  王仲文  ARQ编码通信.北京:机械工业出版社,1991
[4]  Ross Williams, A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS. Document url: http://www.repairfaq.org/filipg/ ,1993

7 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: lzari的源代码(转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:36:12 2000), 转信
发信人: Cloudy (Endless Waltz), 信区: Programming
标  题: lzari的源代码
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 19 18:00:01 2000), 站内信件
    一个对lzss编码过的数据作自适应的0阶arithmetic编码的程序。比
lzh的压缩率要高一点。
/**************************************************************
        LZARI.C -- A Data Compression Program
        (tab = 4 spaces)
***************************************************************
        4/7/1989 Haruhiko Okumura
        Use, distribute, and modify this program freely.
        Please send me your improved versions.
                PC-VAN          SCIENCE
                NIFTY-Serve     PAF01022
                CompuServe      74050,1022
**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/********** 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(int bit)  /* 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(void)  /* 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 into position and length
                                                   if match_length is greate
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 longest match.  These a
re
                        set by the InsertNode() procedure. */
                lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right chi
ldre
&
                        parents -- These constitute binary search trees. */
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.  These 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 that begin with character i.  These are initialized
           to NIL.  Note there are 256 trees. */
        for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;       /* root */
        for (i = 0; i < N; i++) dad[i] = NIL;   /* node */
}
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 longest-match positio
n
           and length via the global variables match_position and
match_length.
           If match_length = F, then 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 < F; 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)) < match_posit
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[lson[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 familiar with arithmetic compression, you should
read
                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  (1UL << 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 int
        sym_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] + 10000 / (i + 200);
                        /* empirical distribution function (quite tentative)
*/
                        /* Please devise a better mechanism! */
}
void UpdateModel(int sym)
{
        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 < sym) {
                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[sym    ]) / 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 < Q1) Output(0);  else Output(1);
        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 < j) {
                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 < j) {
                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 < M + 2; 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_END);
        textsize = ftell(infile);
        if (fwrite(&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 < r; i++) text_buf[i] = ' ';
        for (len = 0; len < F && (c = getc(infile)) != EOF; 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 < last_match_length &&
                                (c = getc(infile)) != EOF; i++) {
                        DeleteNode(s);  text_buf[s] = c;
                        if (s < F - 1) 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++ < last_match_length) {
                        DeleteNode(s);
                        s = (s + 1) & (N - 1);
                        r = (r + 1) & (N - 1);
                        if (--len) InsertNode(r);
                }
        } while (len > 0);
        EncodeEnd();
        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 (fread(&textsize, sizeof textsize, 1, infile) < 1)
                Error("Read Error");  /* read size of text */
        if (textsize == 0) return;
        StartDecode();  StartModel();
        for (i = 0; i < N - F; i++) text_buf[i] = ' ';
        r = N - F;
        for (count = 0; count < textsize; ) {
                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 < j; 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_FAILURE;
        }
        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;
}
--
            .      .-~\
           / `-'\.'    `- :
           |    /          `._
           |   |   .-.        {
            \  |   `-'         `.

8 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: lzss的源代码(转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:36:56 2000), 转信
发信人: Cloudy (Endless Waltz), 信区: Programming
标  题: lzss的源代码
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 19 18:02:06 2000), 站内信件
    lzss的源代码。lzss是一种基于字典的压缩算法,压缩率不高,
但速度很快。
eely.
        Please send me your improved versions.
                PC-VAN          SCIENCE
                NIFTY-Serve     PAF01022
                CompuServe      74050,1022
**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define N                4096   /* size of ring buffer */
#define F                  18   /* upper limit for match_length */
#define THRESHOLD       2   /* encode string into position and length
                                                   if match_length is greate
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 longest match.  These a
re
                        set by the InsertNode() procedure. */
                lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right chi
ldre
&
                        parents -- These constitute binary search trees. */
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.  These 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 that begin with character i.  These are initialized
           to NIL.  Note there are 256 trees. */
        for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
        for (i = 0; i < N; i++) dad[i] = NIL;
}
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 longest-match positio
n
           and length via the global variables match_position and
match_length.
           If match_length = F, then 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 < F; 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[lson[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" representing 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 < r; i++) text_buf[i] = ' ';  /* Clear the buffer with
                any character that will appear often. */
        for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
                text_buf[r + len] = c;  /* Read F bytes into the last F byte
s of
                        the buffer */
        if ((textsize = len) == 0) return;  /* text of size zero */
        for (i = 1; i <= F; i++) InsertNode(r - i);  /* Insert the F strings
,
                each of which begins with one or more 'space' characters.  N
ote
                the order in which these strings are inserted.  This way,
                degenerate trees will be less likely to occur. */
        InsertNode(r);  /* Finally, insert the whole string just read.  The
                global variables match_length and match_position are set. */
        do {
                if (match_length > len) match_length = len;  /* 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 < code_buf_ptr; i++)  /* Send at most
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 < last_match_length &&
                                (c = getc(infile)) != EOF; i++) {
                        DeleteNode(s);          /* Delete old strings and */
                        text_buf[s] = c;        /* read new bytes */
                        if (s < F - 1) text_buf[s + N] = c;  /* If the posit
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 po
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++ < last_match_length) {       /* After the end of
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 < code_buf_ptr; i++) putc(code_buf[i], outfile
);
                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 < N - F; i++) text_buf[i] = ' ';
        r = N - F;  flags = 0;
        for ( ; ; ) {
                if (((flags >>= 1) & 256) == 0) {
                        if ((c = getc(infile)) == EOF) break;
                        flags = c | 0xff00;             /* uses higher byte
clev
rly */
                }                                                       /* t
o co
nt eight */
                if (flags & 1) {
                        if ((c = getc(infile)) == 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_FAILURE;
        }
        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;
}
--

9 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: RC5算法(转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:33:08 2000), 转信
标  题: RC5算法
发信站: 逸仙时空 Yat-sen Channel (Sat Apr 22 00:11:30 2000), 站内信件
    我最常用的分组算法之一,使用最大长度为256字节的变长密码。
RC5接受两个参数r:循环的次数,b:以word计算密码长度。
初始化子密钥数组S[2*r+2]:
定义P=0xb7e15163,Q=0x9e3779b9
S[0]=p,S[i]=(S[i+1]+Q) mod power(2,w);
i=j=0;A=B=0;
循环3*max(2*r+2,b)次以下步骤:
  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
加密算法:
  对长度为2words的明文M[2]作以下变换,得到密文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]
解密算法:
  对长度为2words的密文C[2]作以下变换,得到明文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]
--

10 楼

发信人: Marslv (梦幻人生), 信区: Program
标  题: Win95 PWL文件password加密算法(转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:31:51 2000), 转信
           Win95 PWL文件password加密算法
最近研究了一下Win95/WFWG3.11之PWL文件,因为前面曾有一个glide.c程序能解出PWL文件的一些资源,但却无法给出Password. 用SoftICE跟了几回,发现涉及password的代码均在MSPWL32.DLL中,以下的程序为将其汇编码翻译成C所成。
  尽管加密算法研究出来了,但破解方法却不大好弄(我觉得一个好的加密算法应该 是没有比穷举法更优的解密方法的,若哪位大虾有好的破解方法,不妨POST上来共同 讨论) 但此password得到方法好象只有技术意义,毕竟解出来泥并不能得到root权限, 而只是别人的Preference Settings! :-(  关于PWL文件的一些说明:14个字符长的密码(均转为大写),用它生成一个32位的 密钥,由以下算法求得一个XOR串,接下来用此XOR串 XOR 20 bytes长的UserName(也 转为大写), 结果存于PWL文件offset 0x208-0x21B, 0x21C开始为一系列指
向鬃试串的 指针(当然已XOR过了)。资源串中保存的主要是该USER的一些Shared Directory的口令, 资源串也分别与XOR串 XOR, PWL文件.
  // ================= CRYPT.CPP  1997.8.16 ================
#include <stdio.h>
#include <ctype.h>
#include <string.h>
/* 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 according to the password(capital)
// translate from MSPWL32.DLL's codes beginning at 7FCB1972h
unsigned long GenerateKey(char *pw)
{
     int i, len;
     unsigned long sum = 0;
     len = strlen(pw);
     for(i = 0; i <= len; i++)
     {
         sum += toupper(pw[i]);
         sum = (sum << 0x7) | (sum >> 0x19);
         // same as rol sum,7
     }
     return sum;
}
// translate from MSPWL32.DLL's codes 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 codes 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 used 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 < len; 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;
}
--
          .  \ |                /
        ~-.`. \|            .-~_
           `.\-.\       .-~      \
             `-'/~~ -.~          /
           .-~/|`-._ /~~-.~ -- ~
          /  |  \    ~- . _\

我来回复

您尚未登录,请登录后再回复。点此登录或注册