- 注册时间
- 2006-2-26
- 最后登录
- 2008-10-24
⑥精研
- 积分
- 2470
|
自己根据Wikipedia上的算法框架东拼西凑,外加参考了某些游戏引擎写了个实现,勉强能运行不过速度实在是!@$#%……请问有没有现成的实现可以参考?或者能对我的算法给点意见吗?
压缩算法:- int *build_next_table(const unsigned char *s, int n, int *t)
- {
- int i = 2;
- int j = 0;
- t[0] = -1;
- t[1] = 0;
- while (i < n)
- {
- if (s[i-1] == s[j])
- t[i++] = ++j;
- else if (j > 0)
- j = t[j];
- else
- t[i++] = 0;
- }
- return t;
- }
- int kmp_match_mask(const unsigned char *s, int ls, int *t, const unsigned char *dic, int dic_start, int dic_pos, size_t dic_mask, int *match_len)
- {
- int m = dic_start;
- int i = 0;
- int max_l = 0;
- int max_ptr = -1;
- build_next_table(s, ls, t);
- do
- {
- if (s[i] == dic[(m+i) & dic_mask] && ((m+i) & dic_mask) != dic_pos)
- {
- i++;
- if (i > max_l)
- {
- max_l = i;
- max_ptr = m;
- if (max_l == ls)
- break;
- }
- }
- else
- {
- m = (m + i - t[i]) & dic_mask;
- if (i>0) i = t[i];
- }
- } while (((m+i) & dic_mask) != dic_start);
- *match_len = max_l;
- return max_ptr;
- }
- size_t LZW_Compress(const unsigned char *src, unsigned char *dest, size_t size)
- {
- size_t src_off = 0;
- size_t dest_off = 0;
- size_t dic_pos = 0xFEE;
- int dic_size = 18;
- unsigned char dic[0x1000];
- unsigned char *out_buf;
- int out_pos, s_len;
- int i,j;
- int next_table[18];
- int match_len, dic_ref;
- memset(dic, 0, 0x1000);
- while (src_off < size)
- {
- out_buf = dest+dest_off;
- out_buf[0] = 0;
- out_pos = 1;
- for (i=0; i<8; i++)
- {
- s_len = size-src_off;
- if (s_len <= 0) break;
- if (s_len > 18) s_len = 18;
- dic_ref = kmp_match_mask(src+src_off, s_len, next_table, dic, 0xFED, dic_pos, 0xFFF, &match_len);
-
- if (match_len < 3)
- {
- out_buf[0] |= (1 << i);
- out_buf[out_pos++] = dic[dic_pos++] = src[src_off++];
- dic_pos &= 0xFFF;
- if (dic_size < 0x1000) dic_size++;
- }
- else
- {
- out_buf[out_pos++] = dic_ref & 0xFF;
- out_buf[out_pos++] = ((dic_ref & 0xF00) >> 4) | ((match_len - 3) & 0xF);
- for (j=0; j<match_len; j++)
- {
- dic[dic_pos++] = src[src_off++];
- dic_pos &= 0xFFF;
- if (dic_size < 0x1000) dic_size++;
- }
- }
- }
- dest_off += out_pos;
- }
- return dest_off;
- }
复制代码 以上算法是根据Wikipedia上面的框架自己写的,字符串匹配算法用了KMP。
解压算法:- size_t LZW_Decompress(const unsigned char *src, unsigned char *dest, size_t src_size, size_t dest_size)
- {
- size_t src_off = 0;
- size_t dest_off = 0;
- size_t dic_pos = 0xFEE;
- unsigned char dic[0x1000];
- size_t var_1010 = 0;
- size_t var_1008;
-
- memset(dic, 0, 0x1000);
-
- while (src_off < src_size)
- {
- var_1010 >>=1;
- if ((var_1010 & 0x0100) == 0)
- {
- var_1010 = src[src_off++] | 0xFF00;
- }
- if ((var_1010 & 0x0001) != 0)
- {
- if (dest_off >= dest_size) return dest_off;
- dest[dest_off++] = dic[dic_pos++] = src[src_off++];
- dic_pos &= 0xFFF;
- }
- else
- {
- size_t eax;
- size_t i;
- eax = src[src_off] | ((src[src_off+1] & 0xF0) << 4);
- src_off++;
- var_1008 = (src[src_off++] & 0x0F) + 2;
- for (i=0; i<=var_1008; i++)
- {
- if (dest_off >= dest_size) return dest_size;
- dest[dest_off++] = dic[dic_pos++] = dic[(eax+i)&0xFFF];
- dic_pos &= 0xFFF;
- }
- }
- }
- return dest_off;
- }
复制代码 以上是参考(可以算是抄了)某引擎的,这个应该没啥问题…… |
|