Author: greg

  • Extended GIT Information in bash PS1

    Extended GIT Information in bash PS1

    This will generate shell similar to this :

    Multiline version:

    ┌──┤ greg: ~/dev/discovery/discovery-agent │ master  ≡  !1 +2 -2  ≡ 2 weeks ago
    └── λ 
    

    Format `branch ≡ changes additions deletions ≡ last commit`
    Example `master ≡ !1 +2 -2 ≡ 2 weeks ago`

    Since we are interested in interactive shells only we will edit `/etc/profile` and add the following

    # Get branch name 
    parse_git_branch() {
        # git branch | grep -Po '(?<=\*\s)(.*)'	
        local branch=$(git branch 2> /dev/null | sed -e '/^[^*]/d' -e 's/* \(.*\)/ \1/')
        # When there is no initial commit, git branch will not return any branches, use a fallback method
        if [ -z "$branch" ]; then 
             branch=$(git status | grep -iPo '(?<=On branch\s)(.*)')
        fi
        echo $branch
    }
    
    parse_git_status() { 
        # changes to existing files
        # 0 = Changed Files, 1 = Additions, 2 = Deletions
        local gitstat=$(git diff --shortstat 2> /dev/null | grep -Po '\d')
        if [ -z "$gitstat" ]; then
    	gitstat="0 0 0"
        fi
       
        # replate \n with blanks
        gitstat=$(echo "$gitstat" | tr '\n' ' ')
        # untracted(??) or added(A) files
        local gitfiles=$(git status --untracked-files=all -s 2> /dev/null | grep -E '??|A' | wc -l)
        echo "$gitstat $gitfiles"
    }
    
    parse_git_hascommit() {
        val=$(git log 2> /dev/null | grep -iPo 'does not have')
        echo "result :: $val"
        if [ -z "$val" ]; then
          echo 0
          return 0
        fi
    
        echo 1
    }
    
    git_status_ps1() {
    	green_light="\e[38;5;82m"                                             
    	red="\e[91m"       
    	blue="\e[34m"
    	reset="\e[0m"      
    
    	inrepo=$(git rev-parse --is-inside-work-tree 2>/dev/null)         
    	if [ -z "$inrepo" ]; then 
    	   exit
            fi
    
    	#hascommit=$(parse_git_hascommit)
    	#echo "has :: $hascommit"i
    	# can't get time unless we have a commit
    
            # capture error 'fatal: your current branch 'master' does not have any commits yet' and don't display time
    	gittime=$(git log -1 --format=%cr 2> /dev/null)                                  	
            gitstat=$(parse_git_status)                                       
    	IFS=' ' read -r -a array <<< $gitstat                               
    
    	if [ -z "${array[0]}" ]; then                                         
    		array[0]=0     
    		array[1]=0     
    		array[2]=0     
    	fi  
    
    	branch_color=$green_light
    	if [ "${array[0]}" -gt "0" ]; then
    	   branch_color=$red
    	fi
    
    	if [ -z "$gittime" ]; then
    	   gittime="never"
    	fi 
            GIT_PS1="$branch_color$(parse_git_branch) $reset ≡ $green_light ~${array[3]}  !${array[0]} +${array[1]} $red-${array[2]} $reset  ≡  $gittime"
    	echo -e $GIT_PS1
    }
    
    
    PS1='┌──┤ \[\033[01;32m\]\u:\[\033[00m\] '
    PS1=$PS1'\[\033[01;34m\]\w\e[0m │ $(git_status_ps1)\n└──  λ '
    
    

    GIST

  • Counting transitions in a bit string

    We need to count a number of transitions in a bit string from 0->1 and 1->0. I needed this in order to determine Uniform Descriptor in Local Binary Patterns(LBP)

    Samples

    0000 0000  (0 Transitions : Uniform)    0x0
    1110 0011  (2 Transitions : Uniform)    0xE3
    0101 0000  (4 Transitions : NonUniform) 0x50
    0000 1010  (4 Transitions : NonUniform) 0xA
    0000 1001  (3 Transitions : NonUniform) 0x9
    

    Sample run (0xE3)

    0x      e3 :      227 :: 00000000000000000000000011100011
    0x      71 :      113 :: 00000000000000000000000001110001
    0x      92 :      146 :: 00000000000000000000000010010010
    Transition : 3
    

    Implemenation

    We are going to shift the value to the right and then XOR it with the original value to get the number of transitions. From there we going to use population count to get the count of the on bits.

    XOR Truth table

    INPUT	         OUTPUT
    -----------------------
    A	B	A XOR B
    0	0	0
    0	1	1
    1	0	1
    1	1	0
    
    template  void bitstr(const T& out) noexcept;
    template  int  popcnt(const T& val) noexcept;
    
    int main()
    {
        // Uniform descriptors
        // 0000 0000  (0 Transitions : Uniform)    0x0
        // 1110 0011  (2 Transitions : Uniform)    0xE3
        // 0101 0000  (4 Transitions : NonUniform) 0x50
        // 0000 1010  (4 Transitions : NonUniform) 0xA
        // 0000 1001  (3 Transitions : NonUniform) 0x9
    
        int a = 0xE3;
        int b = a >> 1;
        int c = a ^ b;
        int count = popcnt(c);
    
        bitstr(a);
        bitstr(b);
        bitstr(c);
    
        std::cout << "Transition : " <<count; return="" 0;="" }="" template="" <class="" t="">
    int popcnt(const T& val) noexcept
    {
        int bitcount;
        __asm__ ("popcnt %1, %1" : "=r" (bitcount) : "0" (val));
        return bitcount;
    }
    
    template 
    void bitstr(const T& out) noexcept
    {
        std::bitset bs(out);
        auto val =  static_cast(out);
        std::cout << "0x"
                  << std::setw(8) << std::hex << val << " : "
                  << std::setw(8) << std::dec << val<< " :: " << bs << std::endl;
    }
    </count;>

    Gist

  • Hamming distance calculation

    This is a small snippet of how to calculate hamming distance in cpp with small bit of assembly for doing a population count.

    Code

    typedef unsigned long long   hash_t; 
    
    #include 
    #include 
    
    int popcount64(const hash_t& val) noexcept
    {
        int ret;
        __asm__ ("popcnt %1, %1" : "=r" (ret) : "0" (val));
        return ret;
    }
    
    int hamming_distance(const hash_t& x, const hash_t& y)
    {
        auto z = x ^ y;
        auto p = popcount64(z);
    
    #ifdef  DEBUG
        std::cout<<"size  : " << sizeof(hash_t) << std::endl;
        std::cout<<"x val : " << std::bitset<sizeof(hash_t)>(x) << std::endl;
        std::cout<<"y val : " << std::bitset<sizeof(hash_t)>(y) << std::endl;
        std::cout<<"z val : " << std::bitset<sizeof(hash_t)>(z) << std::endl;
        std::cout<<"pop   : " << p << std::endl;
    #endif
    
        return p;
    }
    </sizeof(hash_t)></sizeof(hash_t)></sizeof(hash_t)>

    Usage

        hash_t hash1 = 123456;
        hash_t hash2 = 123456;
    
        int  distance = hamming_distance(hash1, hash2);
        std::cout<<"Hamming : " << distance <<"\n";
    

    Results for sample runs

    Same hashes so we expect our distance to be 0.
    hash1 = 123456
    hash2 = 123456

    size  : 8
    x val : 01000000
    y val : 01000000
    z val : 00000000
    pop   : 0
    
    Hamming : 0
    

    Small difference in hashes.
    hash1 = 123456
    hash2 = 123455

    size  : 8
    x val : 01000000
    y val : 00111111
    z val : 01111111
    pop   : 7
    
    Hamming : 7
    

    Medium difference in hashes.
    hash1 = 123456
    hash2 = 223455

    size  : 8
    x val : 01000000
    y val : 11011111
    z val : 10011111
    pop   : 10
    
    Hamming : 10
    

    Large difference in hashes.
    hash1 = 12345678
    hash2 = 23445671

    size  : 8
    x val : 01001110
    y val : 10100111
    z val : 11101001
    pop   : 14
    
    Hamming : 14
    

    code gist

    Reference :
    https://en.wikipedia.org/wiki/Hamming_distance

  • Histogram Comparison for Image Analysis

    DRAFT

    This is the first article in the series on Image Comparison using Local Binary Patterns.
    Complete code is on github lbp-matcher

    We will start off by looking at different methods of comparing histograms.

    • Histogram Intersection
    • Log Likehood
    • Chi Squared
    • Kullback Leibler Divergence

    All our operations will be performed on 8bpp(bits per pixel) images anything that is not in that format will be up and down converted accordingly.

    Model representation is very simple it contains nothing more than a simple array of bins that will contain our histogram data. As we build the system the model might change.
    Our model will contain 256 bins each bin representing gray intensity in 8 bpp image with 0 being black and 255 being white.

    struct LBPModel
    {
        static const int_t bin_size = 256;
        int_t bins[bin_size] = {};
    };
    

    Histogram Intersection

    This is the basic method of comparing two histograms. The idea here is to take the minimum value of the two bins.

    Histogram Intersection
    [latex](a,b)\;=\sum\nolimits_{i=1}^nmax(a_i,\;b_i)[/latex]

    Histogram intersection in normalized form between 0..1;

    [latex]
    (a,b)\;=\;\frac{\sum_{i=1}^n(a_i,b_i)}{max(\sum_{i=1}^na,\sum_{i=1}^nb)\;}
    [/latex]

    Complete equation with branchless execution and normalization. Branchless execution can provide us with two benefits first there is no IF condition checking so we could gain performance but not necessarily, second it prevents timing attack analysis. Here we are only interested in performance. We will take a look at the generated assembly down the road and do quick performance analysis of our algorithm.

    [latex](a,b)\;=\;\frac{\frac12\sum_{i=1}^n(a_i+b_i\;-\;\vert a_i-b_i\vert)}{max(\sum_{i=1}^na,\sum_{i=1}^nb)\;}[/latex]

    Here we have couple examples of how this calculation was actually performed. This has been copied from the excel spreadsheet which can be found in the git repo.
    Example 1 – High similarity

    Bin[a]	Bin[b]	Result
    1	1	2       = A2+B2-ABS(A2-B2)
    2	2	4       = A3+B3-ABS(A3-B3)
    3	3	6
    4	4	8
    5	5	10
    		
    Value    	15.00   =  0.5 * SUM(C2:C6) 
    Normalized	1.0     =  C8 / MAX(SUM(A2:A6), SUM(B2:B6))
    

    Example 2 – Medium similarity
    In this example bin[b] has couple different values but it is still pretty close.

    Bin[a]	Bin[b]	Result
    1	2	2
    2	2	4
    3	3	6
    4	4	8
    5	2	4
    		
    Value    	12.00
    Normalized	0.8
    

    Example 3 – Low similarity
    Here our histograms are quite different so our similarity is very low.

    Bin[a]	Bin[b]	Result
    1	20	2
    2	2	4
    3	3	6
    4	4	8
    5	20	10
    		
    Value	15.00
    Normalized	0.3
    

    Implementation

    double HistogramComparison::scoreHistogramIntersection(const LBPModel &model, const LBPModel &sample) const
    {
        double d = 0,s1 = 0,s2 = 0;
    
        // branch less execution
        for (int_t i = 0; i < model.bin_size; ++i)
        {
            d  += model.bins[i] + sample.bins[i] - std::abs(model.bins[i] - sample.bins[i]);
            s1 += model.bins[i];
            s2 += sample.bins[i];
        }
    
        return (0.5 * d) / std::fmax(s1, s2);
    }
    

    Log Likelihood

    Implementation

    double HistogramComparison::scoreLogLikelihood(const LBPModel &model, const LBPModel &sample) const
    {
        double d = 0;
        for (int_t i = 0; i < model.bin_size; ++i)
        {
            if (model.bins[i] > 0)
            {
                d += sample.bins[i] * std::log(model.bins[i]);
            }
        }
        return -d;
    }
    

    Chi Squared

    Implementation

    double HistogramComparison::scoreChiSquared(const LBPModel &model, const LBPModel &sample) const
    {
        double d = 0;
        for (int_t i = 0; i < model.bin_size; ++i)
        {
            double q = sample.bins[i] + model.bins[i];
            if (q != 0)
            {
                double d1 = std::pow(sample.bins[i] - model.bins[i], 2);
                d += d1 / q;
            }
        }
        return d;
    }
    

    Kullback Leibler Divergence

    Implementation

    double HistogramComparison::scoreKullbackLeiblerDivergence(const LBPModel &model, const LBPModel &sample) const
    {
        double d = 0;
        for (int_t i = 0; i < model.bin_size; ++i)
        {
            double p = model.bins[i];
            double q = sample.bins[i];
    
            if (p != 0 && q != 0)
            {
                d += p * std::log(p / q);
            }
        }
        return d;
    }
    

    References :
    http://www.ariel.ac.il/sites/ofirpele/publications/ECCV2010.pdf
    https://en.wikipedia.org/wiki/Grayscale
    https://en.wikipedia.org/wiki/Likelihood_function
    https://www.mathjax.org/
    http://www.imatheq.com/imatheq/com/imatheq/math-equation-editor.html
    http://www.wiris.com/editor/demo/en/mathml-latex

  • Image Comparison using Local Binary Patterns

    This is a series of small articles on Image Comparison using Local Binary Patterns.
    Topics I like to cover will include

    • Histogram Comparsion
    • Local Binary Patterns
    • Perceptual Hashing

    From there we will go into building a system that can recognize same words/images in a document.

  • Dump leptonica pix data to console

    Small utility for dumping Leptonica Pix data to the screen.

    void dump(PIX* pix)
    {
        int_t w = pix->w;
        int_t h = pix->h;
    
        int_t wpl = pixGetWpl(pix);
        l_uint32* data = pixGetData(pix);
        l_uint32* line;
    
        printf("\n");
        printf("Depth : %d \n", pix->d);
    
        for (int_t y = 0; y < h; ++y)
        {
            printf("%04d  :  ", y);
            line = data + y * wpl;
            for (int_t x = 0; x < w; ++x)
            {
                l_uint32 val = 0;
    
                if(pix->d == 1)
                    val = GET_DATA_BIT(line, x);
                else if(pix->d == 2)
                    val = GET_DATA_DIBIT(line, x);
                else if(pix->d == 4)
                    val = GET_DATA_QBIT(line, x);
                else // 8, 16, 32
                    val = GET_DATA_BYTE(line, x);
    
                printf("%03d ", val);
            }
            printf("\n");
        }
    }
    
  • Fingerprint cannot be generated while adding new ssh key in GitLab

    This applies to Windows only machines.

    I have GitLab running and was adding a new ‘ssh key’ from windows that was generated using a standard ssk-keygen command but was reciving following error:

    “Fingerprint cannot be generated”

    Command used to generate key:

     ssh-keygen -t rsa -C "gbugaj@localhost" -b 4096
    

    This produces a key in ‘id_rsa.pub’ file, from there I cated that file and copies the content of if by ‘HIGHLIGHTING’ directly in the command window.

    This is the result that got when pasted it

    ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDuer2ZkTKwsirssZTBaJiyr/GpALglr6X9Ct2cysvgYs05SEvz+B66US4bFv5IVwiOEXJ51oR0EF0/oDv4Juq1zzvydX44rdKFwlL7Qq7Uezxw4FCJotn/wZqpuaScNszP8/gvZY82j9HCYmITFWobwk1JGvQnezbZ
    KsaUtUEQwnptYbWvOZ9yNRRzwkntafOBS2l18wJNl6bjHHUJ6NIzRMudvd7/AjqP5qWL3GjJ9ecyHU0Dox3fIAfzlMRhKCQswPos7i35GWtLBzaOfeqJ2iZA2eGjfh1cGW71hyvO72+rxjjXk3uUvSqFP+WWSrt8VdJJqXfhk0RFqDxcUku6fRWeALp0qWna6Qm8/CbF
    rw0t0s0bF557GqaJCIyMEqj+OVMpcMYCTStnjuTNM8OIz/A3BCJbwt9GsojyFUYesfA0i/4tt9MPYAfcPxO914IYn3mq7Qcvq7RgTJPgM8SGY+SIpACjFKaF6wOf91oa105PcPY4yvISLa40GivN0K871yjo/2Jwq6w6ZE601LD0FngWhrfKejueKucvNvYtdR/aX7LL
    Oq6md0HK6ybIGKJH2qph3+GJP/AUAf85bhWe1mPw3woZ28bWjo+Kp5zeTJqtd6QTDWTkDftsQJcmMgT43lViJBqChTTA/oGiXiV62PMKMeMCDaTYNkuZZvLE8Q== gbugaj@localhost
    

    As you see here lines are split, this is the problem. To solve this we just need to open the file in some editor and copy it from there so all the text is on one line.

    ssh-rsa AAAB3NzaC1yc2EAAAADAQABAAACAQDuer2ZkTKwsirssZTBaJiyr/GpALglr6X9Ct2cysvgYs05SEvz+B66US4bFv5IVwiOEXJ51oR0EF0/oDv4Juq1zzvydX44rdKFwlL7Qq7Uezxw4FCJotn/wZqpuaScNszP8/gvZY82j9HCYmITFWobwk1JGvQnezbZ
    KsaUtUEQwnptYbWvOZ9yNRRzwkntafOBS2l18wJNl6bjHHUJ6NIzRMudvd7/AjqP5qWL3GjJ9ecyHU0Dox3fIAfzlMRhKCQswPos7i35GWtLBzaOfeqJ2iZA2eGjfh1cGW71hyvO72+rxjjXk3uUvSqFP+WWSrt8VdJJqXfhk0RFqDxcUku6fRWeALp0qWna6Qm8/CbFrw0t0s0bF557GqaJCIyMEqj+OVMpcMYCTStnjuTNM8OIz/A3BCJbwt9GsojyFUYesfA0i/4tt9MPYAfcPxO914IYn3mq7Qcvq7RgTJPgM8SGY+SIpACjFKaF6wOf91oa105PcPY4yvISLa40GivN0K871yjo/2Jwq6w6ZE601LD0FngWhrfKejueKucvNvYtdR/aX7LLOq6md0HK6ybIGKJH2qph3+GJP/AUAf85bhWe1mPw3woZ28bWjo+Kp5zeTJqtd6QTDWTkDftsQJcmMgT43lViJBqChTTA/oGiXiV62PMKMeMCDaTYNkuZZvLE8Q== gbugaj@localhost
    
  • Overloading by return value in C++

    Here we have a method that allows us to determine return parameter type using templates and operator overloading in C++. This is something that I needed for a project that I am working on where a method call would give me the expected type based on the return type.

    Usage

    There is two way of using this. First one is by calling the para method and second one is by invoking the conversion method directly parameter.
    Personally, I prefer the first one as this one allows me to use it with auto keyword.

    
    std::string p0   = param<std::string>(arguments, 0);
    auto        p0_a = param<std::string>(arguments, 0);
    
    int         p1   = param<int>(arguments, 1);
    auto        p1_a = param<int>(arguments, 1);
    
    // Invoking parameter conversion directly
    std::string p0_p = parameter(arguments, 0); 
    int         p1_p = parameter(arguments, 1);
    

    Implemenation

    struct parameter
    {
    	parameter(const CefV8ValueList & arguments, int index) 
    		:_arg (arguments.at(index)) 
    	{
    	};
    
    	operator std::string() { return _arg->GetStringValue().ToString(); }
    	operator int() { return _arg->GetIntValue();}
    	operator bool() { return _arg->GetBoolValue(); }
    	operator double() { return _arg->GetDoubleValue();}
    
    	CefRefPtr _arg;
    };
    
    template
    T param(const CefV8ValueList & arguments, int index)
    {
    	return parameter(arguments, index);
    }
    

    Reference :
    http://en.cppreference.com/w/cpp/language/cast_operator

  • Kryo (missing no-arg constructor): java.nio.HeapByteBuffer

    While serializing ByteBuffer using Kryo we will run into the following issue.

    Class cannot be created (missing no-arg constructor): java.nio.HeapByteBuffer

    To fix this we can create a custom serializer that will take a ByteBuffer and serialize it to and from Kryo. Serializer is rather simple all we need is two pieces of data, length of the buffer and actual buffer.

    public class ByteBufferSerializer extends Serializer
    {
    
        @Override
        public void write(final Kryo kryo, final Output output, final ByteBuffer object)
        {
            output.writeInt(object.capacity());
            output.write(object.array());
        }
    
        @Override
        public ByteBuffer read(final Kryo kryo, final Input input, final Class type)
        {
            final int length = input.readInt();
            final byte[] buffer = new byte[length];
            input.read(buffer, 0, length);
    
            return ByteBuffer.wrap(buffer, 0, length);
        }   
    }
    
    

    Last step is to register out new serializer with Kryo.

     
    kryo.register(ByteBuffer.allocate(0).getClass(), new ByteBufferSerializer()); 
    

    Here we use a small trick ByteBuffer.allocate(0).getClass() to get concrete implementation of the ByteBuffer. We have to do this because java.nio.HeapByteBuffe is package protected and we can’t get access to it outside the java.nio package.

  • EventEmitter

    Our EventEmitter in PhantomSQL is based on NodeJS version so they should be compatible. Here are couple examples on how to use the emitter.

    Basic usage of registering and listening to an event.

    "use strict";
    
    const {EventEmitter} = require('events');
    
    // Dump all the args
    em.on('hello-event', (...arg)=> {console.info("Hello event handler : " + arg)});
    // Handler without args
    em.on('hello-event', ()=> {console.info("Another handler")});
    // passed in arguments
    em.on('hello-event', (id, val)=> {console.info("Handler :"+id +", "+ val)});
    
    // emit event
    em.emit('hello-event', 123, 'ABC');
    

    A more typical example would be to extend via prototype.

    "use strict";
    const {EventEmitter} = require('events');
    
    function HelloService()
    {
    	// Extends via prototype
    	Object.setPrototypeOf(HelloService.prototype, EventEmitter.prototype);
    	
    	this.hello = function()
    	{
    		console.info("Hello service called");
    		this.emit('hello');
    	}
    }  
    
    const service = new HelloService();
    
    service.on('hello', ()=> {console.info("Hello Handler called")});
    service.hello();