forked from AugmentedRealityCenter/ShelvARApi
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHuffmanEncoder.php
More file actions
97 lines (83 loc) · 2.25 KB
/
Copy pathHuffmanEncoder.php
File metadata and controls
97 lines (83 loc) · 2.25 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
<?php
//Include the associative array that contains the Huffman code
require("huffman-v1.php");
function huffman_encode($input){
global $huffman1;
$ret = "";
$input = trim($input);
for($i=0;$i<strlen($input);$i++){
$ret .= $huffman1[ord(substr($input,$i))];
}
$ret .= $huffman1[0];//Strings should be null terminated when encoded
return $ret;
}
//Find the first Huffman codeword that has the search string
// as a prefix
//TODO: This is stupidly inefficient. Improve using a trie-based
// decoder.
function huffmanSearch($input){
global $huffman1;
for($i=0;$i<256;$i++){
if(strpos($huffman1[$i],$input)===0){
return $i;
}
}
return -1;
}
function huffman_decode($input){
$ret="";
while(strlen($input) > 0){
//What is the length of the longest prefix that is in the table?
$prefixLen=0;
for($prefixLen=1; $prefixLen<strlen($input);$prefixLen++){
$which = huffmanSearch(substr($input,0,$prefixLen));
if($which == -1){
$prefixLen--;
break;
}
}
//If prefixLen is 0, it means we are not making progress. Better abort.
if($prefixLen <= 0) {
return "";
}
$which = huffmanSearch(substr($input,0,$prefixLen));
//Reached the null terminator, so we can return the result.
if($which == 0) return $ret;
$ret .= chr($which);
$input = substr($input,$prefixLen);
}
//Looks like the string wasn't null terminated. Better abort.
return "";
}
/*
//=====================================================================
//Tester. Comment out when using this file in production code.
//Does encode and decode work for all characters from a US keyboard?
function test1(){
$toTest = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./ ~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>?";
$encoded = encode($toTest);
$decoded = decode($encoded);
$passed = (strcmp($toTest,$decoded) == 0);
if($passed){
print("test1 passed<br/ >");
} else {
print("test1 failed<br/ >");
}
}
//Test to see if whitespace trimming is working
function test2(){
$toTest = " cow \t\n\t";
$e = encode($toTest);
$d = decode($e);
$passed = (strcmp($d,"cow") == 0);
if($passed){
print("test2 passed<br/ >");
} else {
print("test2 failed<br/ >");
}
}
//Main
test1();
test2();
*/
?>