faster_bytecode.cc

/*

    This file is part of the FAST-ER machine learning system.
    Copyright (C) 2008  Edward Rosten and Los Alamos National Laboratory

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#include "faster_bytecode.h"
#include <cvd/image.h>
#include <cerrno>

///\cond never
using namespace CVD;
using namespace std;
///\endcond

#ifdef JIT
#include <sys/mman.h>
///This struct contains a x86 machine-code compiled version of the detector. The detector
///operates on a single row and inserts offset from the beginning of the image in to a 
///std::vector. 
///@ingroup gFastTree
class jit_detector
{
	public:
		

		///Run the compiled detector on a row of an image.
		///@param im The image.
		///@param row The row to detect corners in.
		///@param xmin The starting position.
		///@param  xmax The ending position.
		///@param corners The detected corners as offsets from image.data().
		///@param threshold The corner detector threshold.
		void detect_in_row(const Image<byte>& im, int row, int xmin, int xmax, vector<int>& corners, int threshold)
		{

			const byte* p = im[row] + xmin;
			const int n = xmax - xmin;
			void* cs = &corners;
			const void* im_data = im.data();
			/* r/m usage, at entry to machine code
				In use:
					%ecx				Num remaining
					%edi 				threshold
					%ebp 			    Detect in row machine code procedure address
					%ebx				cb
					%edx				c_b
					%esi				data
					%eax				Scratch

					4%esp 				%esi: produced automatically by call
					8%esp				image.data()
					12%esp				&vector<int>
					16%esp				vector_inserter: simple function for calling member of std::vector


				Input:	
					0 num remaining
					1 data pointer
					2 threshold
					3 proc 
					4 push_back_proc
					5 vector<int>
					6 image.data()
			*/

			__asm__ __volatile__(
				//Save all registers
				"	pusha								\n"
				
				//Load operands in to correct places
				"	pushl			%4					\n"
				"	pushl			%5					\n"
				"	pushl			%6					\n"
				"	movl			%0, %%ecx			\n"	
				"	movl			%1, %%esi			\n"
				"	movl			%2, %%edi			\n"
				" 	movl			%3, %%ebp			\n"   //%? uses ebp, so trash ebp last

				
				//Start the loop
				"	cmp				$0, %%ecx			\n"
				"	je				1					\n"
				"	call			*%%ebp				\n"
				"1:										\n"


				//Unload operands
				"	popl			%%eax				\n"
				"	popl			%%eax				\n"
				"	popl			%%eax				\n"

				//Restore all registers
				"	popa								\n"
				:
				: "m"(n), "m"(p), "m"(threshold), "m"(proc), "i"(&vector_inserter), "m"(cs), "m"(im_data)
			);


		}


		///Create a compiled detector from the bytecode.
		///@param v Bytecode.
		jit_detector(const vector<block_bytecode::fast_detector_bit>& v)
		{
			//blocksize
			const int bs=28;

			length = bs * (v.size() + 2); //Add head and tail block

			/* The original assembler code looked like this
			   This is now done in machine code, with the whole tree in
			   place of  line 0x804e0c1.

			 804e0b3:	83 f9 00             	cmp    $0x0,%ecx
			 804e0b6:	74 1b                	je     804e0d3 <finished>

			0804e0b8 <loop>:
			 804e0b8:	0f b6 16             	movzbl (%esi),%edx
			 804e0bb:	89 d3                	mov    %edx,%ebx
			 804e0bd:	29 fa                	sub    %edi,%edx
			 804e0bf:	01 fb                	add    %edi,%ebx
			 804e0c1:	ff d5                	call   *%ebp
			 804e0c3:	a8 ff                	test   $0xff,%al
			 804e0c5:	74 08                	je     804e0cf <nocorner>
			 804e0c7:	56                   	push   %esi
			 804e0c8:	51                   	push   %ecx
			 804e0c9:	ff 54 24 10          	call   *0x10(%esp)
			 804e0cd:	59                   	pop    %ecx
			 804e0ce:	58                   	pop    %eax

			0804e0cf <nocorner>:
			 804e0cf:	46                   	inc    %esi
			 804e0d0:	49                   	dec    %ecx
			 804e0d1:	75 e5                	jne    804e0b8 <loop>			//jne == jnz

		  	Unused spaces are filled in with int $3, (instruction 0xcc), which
			causes a debug trap. Makes catching errors easier.
			
			The consists of fixed sized blocks pasted together. The size is determined by the
			largest block, which is a tree node. This makes jump computation trivial, but 
			it also means that short jumps are never used, and the code is therefore larger
			than necessary.

			The rest have 0xcc filled in in the spare places. 

			The blocks are templates and have the relevant parts filled in prior to 
			copying.

			Each tree node (including leaves are represented by an entire block)

			Detectod corners are inserted in to a vector<int> as the integer offset of the corner
			pixel from the beginning of the image
			*/

			const unsigned char loop_head[bs] = 
			{
				0xEB, 0x11,							//jmp + 17

				0xcc,0xcc,0xcc,0xcc,0xcc,0xcc,		//dead space
				0xcc,0xcc,0xcc,0xcc,0xcc,0xcc,
				0xcc,0xcc,0xcc,0xcc,0xcc,


				0x0f, 0xb6, 0x16,					//movzbl (%esi),%edx			Load data
				0x89, 0xd3,                			//mov    %edx,%ebx
				0x29, 0xfa,                			//sub    %edi,%edx				Compute c_b
				0x01, 0xfb,                			//add    %edi,%ebx				Compute cb
			};
			const int loop_head_start=19;			//Jump to here to continue loop


			unsigned char loop_tail[bs] = 
			{
				0x56,								//push %esi				Functions seem to trash this otherwise
				0x51,								//push %ecx				Functions seem to trash this otherwise
				0xFF, 0x54, 0x24, 0x14,				//call *16(%esp)		Other arguments on the stack already
				0x59,								//pop %ecx				Clean stack
				0x58,								//pop %eax				...
				
				0x46,								//inc %esi
				0x49,								//dec %ecx
				0x0F, 0x85, 0xcc, 0xcc, 0xcc, 0xcc,	//jnz <back to first block>

				0xc3, 								//ret
				0xcc,0xcc,0xcc,0xcc,  				//dead space 
				0xcc,0xcc,0xcc,0xcc,
				0xcc,0xcc,0xcc,
			};
			const int loop_tail_address_offset = 12;   //fill in the jump <back to first block> address here
			const int loop_tail_jump_delta     = 16;   //Jump block_size*depth + this, to loop.
			const int loop_tail_entry		   = 8;    //jump to here to avoid inserting current point as corner

			unsigned char cont_or_goto[bs] = 
			{	
				0xE9,0xcc, 0xcc, 0xcc, 0xcc,		//Jump to end of loop
				0xcc,0xcc,0xcc,0xcc,0xcc,0xcc, 		//dead space
				0xcc,0xcc,0xcc,0xcc,0xcc,0xcc,
				0xcc,0xcc,0xcc,0xcc,0xcc,0xcc,
				0xcc,0xcc,0xcc,0xcc,0xcc
			};
			const int cont_jmp_addr = 1;			//Jump address filled in here
			const int cont_delta = 5;				//This much in addition to block delta
			
			unsigned char branch[bs] = 
			{
				0x0f, 0xB6, 0x86, 0xcc, 0xcc, 0xcc, 0xcc, 	//movzbl   OOOO(%esi),%eax
				0x39, 0xd8,									//cmp      %ebx, %eax   (eax - ebx) = (data[##]-cb
				0x0F, 0x8F, 0xcc, 0xcc, 0xcc, 0xcc,			//jg       XXXX         jmp by XXXX if eax > ebx
				0x39, 0xC2,									//cmp      %eax, %edx   (edx - eax) = c_b - data[##]
				0x0F, 0x8F, 0xcc, 0xcc, 0xcc, 0xcc,			//jg       YYYY         jmp by YYYY if ecx > ebx
				0xE9, 0xcc, 0xcc, 0xcc, 0xcc,				//jmp	   ZZZZ			Unconditional jump to ZZZZ
			};
			const int block_off_off = 3;
			const int block_gt_off = 11;
			const int block_lt_off = 19;
			const int block_eq_off = 24;


			//mmap a writable, executable block of memory for JITted code
			proc = (unsigned char*) mmap(0, length, PROT_EXEC | PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
			if(proc == MAP_FAILED)
			{
				cerr << "mmap failed with error: " << strerror(errno) << endl;
				exit(1);
			}
			
			//Copy in the loop head: no parts to be filled in.
			memcpy(proc, loop_head, bs);

			for(int i=0; i < (int)v.size(); i++)
			{
				if(v[i].lt == 0)			// leaf
				{
					if(v[i].gt == 0) //Fill in jump to continue part
					{
						*(int*)(cont_or_goto + cont_jmp_addr) = bs * (v.size()- i) - cont_delta + loop_tail_entry;
					}
					else //fill in jump to insert part
					{
						*(int*)(cont_or_goto + cont_jmp_addr) = bs * (v.size() - i) - cont_delta;
					}
						

					memcpy(proc + (i+1)*bs, cont_or_goto, bs);
				}
				else
				{
					*(int*)(branch+block_off_off)  = v[i].offset;

					//Optimization: leaf nodes have a non-conditional goto in them
					//so goto the right place directly, rather than the leaf node.
					//This has a 5% effect or so, so bigger gains elsewhere.
					//Removed for simplicity.
					
					*(int*)(branch+block_gt_off) = (v[i].gt -i) * bs - (block_gt_off + 4);
					*(int*)(branch+block_lt_off) = (v[i].lt -i) * bs - (block_lt_off + 4);
					*(int*)(branch+block_eq_off) = (v[i].eq -i) * bs - (block_eq_off + 4);

					memcpy(proc + (i+1)*bs, branch, bs);
				}
			}
			
			//Insert the correct backwards jump for looping
			*(int*)(loop_tail+loop_tail_address_offset) = -bs * (1+v.size()) - loop_tail_jump_delta + loop_head_start;
			memcpy(proc + bs * (v.size() + 1), loop_tail, bs);

		}

		///Destroy object, unmapping executable memory.
		~jit_detector()
		{
			munmap(proc, length);
		}

	private:
		///Prevent copying
		void operator=(const jit_detector&);
		///Prevent copying
		jit_detector(const jit_detector&);

		unsigned char* proc;			///< The machine code is stored in this mmap() allocated data which allows code execution.
		int			   length;			///< Number of mmap() allocated bytes.

		///Callback function to allow insertion in to std::vector. The execution of this function
		///relies on the stack having the following layout (stack head on the left):
		///@code
		///return_address first_arg second_arg etc...
		///@endcode
		///so that the arguemnts directly reflect the stack layout.
		///For speed, and in order to minimize stack handling, the argument list spans two call instructions worth of stack.
		///
		///@param ecx_dummy Pushed by the machine code, since the ABI allows ecx to be trashed
		///@param p The pointer to the current pixel. Pushed by the machine code.
		///@param esp_return_dummy Location to return to on a return from the machine code. Generated by the assembler call in to the machine code.
		///@param im_data Pointer to the first image pixel. Pushed by the assembler caller.
		///@param i  Pointer to the std::vector<int> which stores the data. Pushed by the assembler caller.
		static void vector_inserter(int ecx_dummy, const byte* p, const void* esp_return_dummy, const byte* im_data, vector<int>* i)
		{
			i->push_back(p-im_data);
		}
};
#endif

///Detect corners in an image. The width of the image must match the width the
///detector was compiled to (using tree_elemeent::make_fast_detector for the
///results to make sense. The bytecode is JIT coimpiled if possible.
///@param im The image in which to detect corners
///@param corners Detected corners are inserted in to this container.
///@param threshold Corner detector threshold to use
///@param xmin x coordinate to start at.
///@param ymin y coordinate to start at.
///@param xmax x coordinate to go up to.
///@param ymax y coordinate to go up to.
void block_bytecode::detect(const CVD::Image<CVD::byte>& im, std::vector<int>& corners, int threshold, int xmin, int xmax, int ymin, int ymax)
{
	#ifdef JIT
		jit_detector jit(d);
		for(int y = ymin; y < ymax; y++)
			jit.detect_in_row(im, y, xmin, xmax, corners, threshold);
	#else
		cerr << "Hello!\n";
		for(int y = ymin; y < ymax; y++)
			for(int x=xmin; x < xmax; x++)
				if(detect_no_score(&im[y][x], threshold))
					corners.push_back(&im[y][x] - im.data());
	#endif
}