Demo entry 6362463

c++

   

Submitted by anonymous on May 09, 2017 at 04:26
Language: C++. Code size: 2.7 kB.

/*
 *  =>实现自己的hamming distance计算代码
 *  =>面向图像特征描述子的计算要求
 *    1. feature长度128,256,..千万
 *    2. 实现在海量数据中快速匹配(笨的暴力匹配)
 */


#include <stdio.h>
#include <stdlib.h>

// 使用SSE
#include <nmmintrin.h>  

#define USE_SSE4 1

//定义特征描述子的长度,
#define FEATURE_LENGTH  128

typedef unsigned long long  uint64;
typedef unsigned int        uint32;



//c 实现的简单的hamming distance 计算,原理
int hamming_dis(unsigned x, unsigned y)
{
	int dist;
	unsigned val;

	dist = 0;
	val = x ^ y;  // X OR Y hammming Dis 是异或计算的值中“1”的个数
	
	while(val != 0) //统计val的二进制表示中“1”的个数
	{
	     dist++;
		 val &= val - 1;
	}
	return dist;
}
 
//https://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/
//实现二进制数据并行统计
int BitCount(unsigned int u)
 {
         unsigned int uCount;

         uCount = u
                  - ((u >> 1) & 033333333333)
                  - ((u >> 2) & 011111111111);
         return
           ((uCount + (uCount >> 3))
            & 030707070707) % 63;
 }

// 计算uint64 长度的hamming distance
uint64 _m_hamming_distance_uint64(uint64 x, uint64 y)
{
    uint64 dist;
	uint64 val;

	dist = 0;
	val  =  x ^ y;

	while(val != 0)
	{
	    dist++;
		val &= val - 1;
	}
	return dist;
}



//计算空间长度更长的hamming distance,
int _m_hamming_dis(const unsigned char* x, const unsigned char *y)
{
#ifdef USE_SSE4
	uint64 dist;

	uint64  *xx = (uint64 *)x;
	uint64  *yy = (uint64 *)y;
	dist = 0;
	
	//此处可以尝试添加并行处理!
	for(unsigned i = 0; i <FEATURE_LENGTH /( sizeof(uint64) * 8 ); ++i)
	{
		//dist += _m_hamming_distance_uint64(xx[i],yy[i]);
		//printf("xx, yy, dist = %d, %d, %d\n",dist,xx[i],yy[i]);
		dist += _mm_popcnt_u64(xx[i] ^ yy[i]);
	}
	return (int)dist;
#else
	int dist;

	uint64  *xx = (uint64 *)x;
	uint64  *yy = (uint64 *)y;
	dist = 0;
	
	//此处可以尝试添加并行处理!
	for(unsigned i = 0; i <FEATURE_LENGTH /( sizeof(uint64) * 8 ); ++i)
	{
		//dist += _m_hamming_distance_uint64(xx[i],yy[i]);
		// 或者
		dist += BigCount(xx[i] ^ yy[i])
	}
	return dist;
#endif
}



// 测试函数
int main()
{

	//printf("ham_dis = %d",hamming_dis(4,8));
	
	unsigned  *a = (unsigned *)malloc(256); //256  bit
	unsigned  *b = (unsigned *)malloc(256); //256

	for(unsigned i = 0; i < 256 /(sizeof(unsigned)*8); ++i)
	{
	    a[i] = i + 1;
		b[i] = i + 2;
		printf("a,b = %d,%d\n",a[i],b[i]);
	}

	uint64 *aa = (uint64 *)a;
	uint64 *bb = (uint64 *)b;

	for(unsigned i = 0; i < 256/(sizeof(uint64)*8); ++i)
	{
	    printf("aa,bb = %d, %d\n",aa[i],bb[i]);
	}


	//测试计算长数据hamming dis结果正确
	printf("ham_dis = %d\n",_m_hamming_dis((const unsigned char *)a,(const unsigned char *)b));
	
	system("pause");
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).