Here is some code to get across the basic flow of the algorithm.
1.) Open file, convert hex to binary string/number.
2.) Count ones in string, get index for pattern in subgroup for Binomial Coefficient / Column in Pascal triangle.
3.) Store ones count in an array and index number (as binary) becomes new input data/string.
4.) Goto step 2 using new input until data is exhausted.
PSEUDO-CODE:
function krypton(filePath){ string fileBinary = hexToBinary(filePath);
kompress(fileBinary); }
//VARIABLES, will be used to string together final output.
array kountArray; //counts for each iteraction level
array optimizeArray; //optimize BOOL did flip setting per level
int numberOfOnes; //holds number of ones for current level
string answerIndex; //holds index binary string for current level
array trimmedOnes; //leading ones trimmed
//VARIABLES
//will probably always lead with a 1, may need to //track leading Zero for very first 'file' input
function kompress(inputBinaryString){
//keep looping until answer is single digit 1 or 0 while(inputBinaryString.length > 0) { //determine number of ones in input string numberOfOnes = kountOnes(inputBinaryString); //if string has more ones than zeros, then flip... //ie 10101, transform into 01010 //simple 1-bit replacement based optimize, //could use 2-bit.... or other algorithms. //may need to track trimmed leading 1's if(numberOfOnes > inputBinaryString.length/2) { //store interation = DID flip optimizeArray[] = 1; //flipbits //faster than reparsing numberOfOnes = inputBinaryString.length - numberOfOnes; //flip 1's and 0's for eachother inputBinaryString = flipString(inputBinaryString); } else { //store interaction = did NOT flip optimizeArray[] = 0; //flipbits } //store 1's count kountArray[] = numberOfOnes;
//get index for data pattern within triangle column... answerIndex = indexForPattern(inputBinaryString,numberOfOnes); //iterate, new input is the index in binary kompress(answerIndex); }
}
///// INDEXING CODE BELOW///// INDEXING CODE BELOW
//input 11001, = 3/5 = 10 patterns//INDEX BREAKDOWN00111 = 001011 = 101101 = 201110 = 310011 = 410101 = 510110 = 611001 = 711010 = 811100 = 9//INDEX BREAKDOWN
//ALL THANKS to user 'Paul Miner' of ArsTechnica Forum //for original algorithm used below (July 2005)//arstechnica.com/groupee/forums?a=tpc&f=6330927813&m=787007444731//major speed bottleneck in current form, this function //needs to be refactored/vectorized for neglible speed per loop
function indexForPattern(binaryString, ones){
int encounteredOnes; int onePose; int index; int startPosition; //11001 becomes 10011 string revereString = reverse(binaryString);
index = 0; encounteredOnes = 0; startPosition = 0; //get position of '1' in string revere, start position... //one time scanner to postion array quicker? while (onePose = position('1',revereString,startPosition)) {
//another 1 encountered... sine while resolved to true encounteredOnes++; //add value of binomial coefficient to existing index value; index += binCoe(onePose,encounteredOnes); //new start startPosition = onePose+1;
//LOOP BREAKDOWN, positions //10011 = //1 = pos: 0 //0 = nope //0 = nope //1 = pos: 3 //1 = pos: 4 //LOOP BREAKDOWN, binCoe(onePose,encounteredOnes); //binCoe(0,1); = 0 //binCoe(3,2); = 3 //binCoe(4,3); = 4 //LOOP BREAKDOWN
}
}
///// END INDEXING CODE///// END INDEXING CODE
