%% Normalize Data for Lookup Tables
% This example shows how to normalize data for use in lookup tables.
%
% Lookup tables are a very efficient way to write computationally-intense
% functions for fixed-point embedded devices.  For example, you can efficiently
% implement logarithm, sine, cosine, tangent, and square-root using lookup
% tables.  You normalize the inputs to these functions to produce a
% smaller lookup table, and then you scale the outputs by the normalization
% factor.  This example shows how to implement the normalization function
% that is used in examples 
% <fi_sqrtlookup_8_bit_byte_example.html Implement Fixed-Point Square Root Using Lookup Table>
% and
% <fi_log2lookup_8_bit_byte_example.html Implement Fixed-Point Log2 Using Lookup Table>.

% Copyright 2012-2018 The MathWorks, Inc.
%% 
% *Setup*
%
% To assure that this example does not change your preferences or settings, this
% code stores the original state, and you will restore it at the end.
originalFormat = get(0, 'format'); format long g
originalWarningState = warning('off','fixed:fi:underflow');
originalFiprefState = get(fipref); reset(fipref)

%% Function to Normalize Unsigned Data
% This algorithm normalizes unsigned data with 8-bit bytes.  Given input
% |u > 0|, the output |x| is normalized such that
%
%   u = x * 2^n
%
% where |1 <= x < 2| and |n| is an integer.  Note that |n| may be positive,
% negative, or zero. 
%
% Function |fi_normalize_unsigned_8_bit_byte| looks at the 8
% most-significant-bits of the input at a time, and left shifts the bits until
% the most-significant bit is a 1.  The number of bits to shift for each 8-bit
% byte is read from the number-of-leading-zeros lookup table, NLZLUT.
%
%
%   function [x,n] = fi_normalize_unsigned_8_bit_byte(u) %#codegen
%       assert(isscalar(u),'Input must be scalar');
%       assert(all(u>0),'Input must be positive.');
%       assert(isfi(u) && isfixed(u),'Input must be a fi object with fixed-point data type.');
%       u = removefimath(u);
%       NLZLUT = number_of_leading_zeros_look_up_table();
%       word_length = u.WordLength;
%       u_fraction_length = u.FractionLength;
%       B = 8;
%       leftshifts=int8(0);
%       % Reinterpret the input as an unsigned integer.
%       T_unsigned_integer = numerictype(0, word_length, 0);
%       v = reinterpretcast(u,T_unsigned_integer);
%       F = fimath('OverflowAction','Wrap',...
%                  'RoundingMethod','Floor',...
%                  'SumMode','KeepLSB',...
%                  'SumWordLength',v.WordLength);
%       v = setfimath(v,F);
%       % Unroll the loop in generated code so there will be no branching.
%       for k = coder.unroll(1:ceil(word_length/B))
%           % For each iteration, see how many leading zeros are in the high
%           % byte of V, and shift them out to the left. Continue with the
%           % shifted V for as many bytes as it has.
%           %
%           % The index is the high byte of the input plus 1 to make it a
%           % one-based index.
%           index = int32(bitsra(v, word_length - B) + uint8(1));
%           % Index into the number-of-leading-zeros lookup table.  This lookup
%           % table takes in a byte and returns the number of leading zeros in the
%           % binary representation.
%           shiftamount = NLZLUT(index);
%           % Left-shift out all the leading zeros in the high byte.
%           v = bitsll(v,shiftamount);
%           % Update the total number of left-shifts
%           leftshifts = leftshifts+shiftamount;
%       end
%       % The input has been left-shifted so the most-significant-bit is a 1.
%       % Reinterpret the output as unsigned with one integer bit, so
%       % that 1 <= x < 2.
%       T_x = numerictype(0,word_length,word_length-1);
%       x = reinterpretcast(v, T_x);
%       x = removefimath(x);
%       % Let Q = int(u).  Then u = Q*2^(-u_fraction_length), 
%       % and x = Q*2^leftshifts * 2^(1-word_length).  Therefore,
%       % u = x*2^n, where n is defined as:
%       n = word_length -  u_fraction_length - leftshifts - 1;
%   end
%
%% Number-of-Leading-Zeros Lookup Table
% Function |number_of_leading_zeros_look_up_table| is used by
% |fi_normalize_unsigned_8_bit_byte| and returns a table of the number of
% leading zero bits in an 8-bit word.
%
% The first element of NLZLUT is 8 and corresponds to |u=0|.  In 8-bit value 
% |u = 00000000_2|, where subscript 2 indicates base-2, there are 8 leading zero
% bits.
%
% The second element of NLZLUT is 7 and corresponds to |u=1|.  
% There are 7 leading zero bits in 8-bit value |u = 00000001_2|.
%
% And so forth, until the last element of NLZLUT is 0 and corresponds to
% |u=255|.  There are 0 leading zero bits in the 8-bit value
% |u=11111111_2|.
%
% The |NLZLUT| table was generated by:
%
%   >> B = 8;  % Number of bits in a byte
%   >> NLZLUT = int8(B-ceil(log2((1:2^B))))
%
%   function NLZLUT = number_of_leading_zeros_look_up_table()
%   %   B = 8;  % Number of bits in a byte
%   %   NLZLUT = int8(B-ceil(log2((1:2^B))))
%       NLZLUT = int8([8    7    6    6    5    5    5    5 ...
%                      4    4    4    4    4    4    4    4 ...
%                      3    3    3    3    3    3    3    3 ...
%                      3    3    3    3    3    3    3    3 ...
%                      2    2    2    2    2    2    2    2 ...
%                      2    2    2    2    2    2    2    2 ...
%                      2    2    2    2    2    2    2    2 ...
%                      2    2    2    2    2    2    2    2 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      1    1    1    1    1    1    1    1 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0 ...
%                      0    0    0    0    0    0    0    0]);
%   end
%
%% Example
% For example, let
u = fi(0.3, 1, 16, 8);
%%
% In binary, |u = 00000000.01001101_2 = 0.30078125| (the fixed-point value is not exactly
% 0.3 because of roundoff to 8 bits).  The goal is to normalize such that 
%
% |u = 1.001101000000000_2 * 2^(-2) = x * 2^n|. 
%
% Start with |u| represented as an unsigned integer.
%
%     High byte  Low byte
%      00000000  01001101  Start: u as unsigned integer.
%
% The high byte is |0 = 00000000_2|.  Add 1 to make an index out of it:
% |index = 0 + 1 = 1|.  The number-of-leading-zeros lookup table at index 1
% indicates that there are 8 leading zeros: |NLZLUT(1) = 8|.
% Left shift by this many bits. 
%
%    High byte  Low byte
%     01001101  00000000   Left-shifted by 8 bits.
%
% Iterate once more to remove the leading zeros from the next byte.
%
% The high byte is |77 = 01001101_2|.  Add 1 to make an index out of it:
% |index = 77 + 1 = 78|.  The number-of-leading-zeros lookup table at index 78
% indicates that there is 1 leading zero: |NLZLUT(78) = 1|.
% Left shift by this many bits. 
%
%
%    High byte  Low byte
%    100110100  0000000    Left-shifted by 1 additional bit, for a total of 9.
%
% Reinterpret these bits as unsigned fixed-point with 15 fractional bits.
%
%   x = 1.001101000000000_2 = 1.203125
%
% The value for |n| is the word-length of |u|, minus the fraction length of
% |u|, minus the number of left shifts, minus 1.
%
%  n = 16 - 8 - 9 - 1 = -2.
%
% And so your result is:
[x,n] = fi_normalize_unsigned_8_bit_byte(u)

%%
% Comparing binary values, you can see that x has the same bits as u,
% left-shifted by 9 bits.
binary_representation_of_u = bin(u)
binary_representation_of_x = bin(x)

%% 
% *Cleanup*
%
% Restore original state.
set(0, 'format', originalFormat);
warning(originalWarningState);
fipref(originalFiprefState);
%#ok<*NOPTS>