%
% Function to demonstrate palette sorting
% See webpage documentation for details of the theory
%
% The input is the filename and the image format (usually GIF)
% and the message to hide 
% 

% Note: I use a reverse lookup map. This takes far too much time, 
% must be a better way in matlab. Till then I dont see this method
% being feasible and so have skipped the decode phase (which is trivial)
%
function [image_data, map] = palette_stego(filename, image_type, message)

% read file
[image_data, map] = imread(filename, image_type);

% convert to double
image_data = uint8(double(image_data));

% calculate dimensions 
s = size(image_data);
x = s(1,1);
y = s(1,2);
count = x*y;

% calculate Y component of the YCbCr scale
luminance = 0.299*map(:,1)+ 0.587*map(:,2) + 0.114*map(:,3);

% store map with lumninance
map_old = [luminance map];

% sort the luminance
luminance_new = sort(luminance);

% store it in a new map
map_new = [luminance_new];

% get the size of the map
map_size = size(map);
map_size = map_size(1,1);

% create a reverse lookup between old and new luminances
% old being unsorted, new being sorted
old_new = zeros(map_size,1);
new_old = zeros(map_size,1);
for i = 1:map_size,   
    [x,y] = find(map_new(:,1) == map_old(i,1));
    map_final(x,:) = map_old(i,:);
    old_new(i) = x;
    new_old(x) = i;
end    
    
for i = 1:1:s(1,1),
    for j=1:1:s(1,2),
        image_data(i,j) = old_new(image_data(i,j));
    end
end

% convert message into bits
message = dec2bin(message, 8);
marraysize = size(message);
binmessage ='';
for i = 1:marraysize(1,1),
    binmessage = strcat(binmessage,message(i,:));
end

% get the message size
message_size = size(message);
msize = message_size(1,1)*message_size(1,2);

% generate thr random keys
keys = randperm(msize);
k = keys(1);

pos = zeros(msize,2);
real_counter = 1;
% replace indices based on the ez stego algo
for i = 1:msize,    

    % get a valid pt; till then loop around
    % image
    while 1==1,
        
        
        % calculate 2d x,y from 1d k
        y= mod(k, s(1,2));
        if y == 0, 
            y = s(1,2);
        end
        if floor(k/s(1,2)) < k/s(1,2),
            x = floor(k/s(1,2)) + 1;
        else,
            x = k/s(1,2);           
        end        
    
        if x > s(1,1),
            x = s(1,1);
        end        

        
        % get the image data
        index = image_data(x,y);
        binstr = dec2bin(double(index), 8);
        binstr(1,8) = char(binmessage(real_counter));
        index= bin2dec(binstr);    
        
        % edge cases 
        if index<= 0 | index > map_size,
            k = k + 1;        
        else,
            break
        end          
        
    end 
    
    % here is the crux of the algo
    % get the new position in the sorted 
    % luminance map
    image_data(x,y) = new_old(index);
    pos(real_counter,:) = [x y];
    k = k + keys(real_counter);
    if k > count,
        k = k-count;
    end
    real_counter = real_counter + 1;    
end

% final step
skipped = 0;

% loop through the image
for i = 1:s(1,1),
    for j=1:s(1,2),                   
        found = 0;
        
        % -----
        % THIS IS THE TIME CONSUMING PART
        % 
        % if its a position chosen for hiding
        % then get its index
        % ----
        for k = 1:msize;
            if pos(k,:) == [i j],
                found = 1;
                break;
             end
        end
        if found == 1,
            skipped = skipped + 1;
            continue
        end            
        
        % find the corresponding color vector 
        % (see algo in documentation)
        index = image_data(i,j);
        replace_index=new_old(index);
        image_data(i,j) = replace_index;        
    end
end

% get the image data back
image_data = uint8(double(image_data) - 1);
toc