On Thu, May 08, 2014 at 12:44:57PM +0100, Damien Lespiau wrote:
> I was hoping we could compute a (near) minimal perfect hash function
> though. Let me try to dig a bit.
So, I went a bit further here and we can actually generate a minimal
perfect hash function. I took the 44 HSW render opcodes and fed them
into:
http://burtleburtle.net/bob/hash/perfect.html
https://github.com/driedfruit/jenkins-minimal-perfect-hash
The resulting hash function is:
static uint8_t mph_tab[] = {
0,0,10,0,51,0,34,0,12,22,0,0,28,0,9,0,
9,0,19,0,0,0,11,0,10,61,20,50,49,60,45,55,
};
static uint32_t mph_hash(uint32_t val)
{
uint32_t a, b, rsl;
val += 0xa195a44b;
val += (val << 8);
val ^= (val >> 4);
b = (val >> 18) & 0x1f;
a = val >> 27;
rsl = (a^mph_tab[b]);
return rsl;
}
When used the 44 HSW opcodes (opcode & 0xffff0000) it produces distinct numbers
(perfect hash) from 0 to 43 (minimal) that could then be used to address an array.
You can play with the joined test:
$ ./minimal-hash-hsw-render | sort -nk2
So now, how useful is that is an interesting question. We do have static tables
upstream (IIUC), but Tvrtko reminded me that it may not match other trees,
which is sad.
--
Damien
#include <stdint.h>
#include <stdio.h>
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(*(x)))
#define MI_INSTR(opcode, flags) (((opcode) << 23) | (flags))
#define MI_NOOP MI_INSTR(0, 0)
#define MI_USER_INTERRUPT MI_INSTR(0x02, 0)
#define MI_WAIT_FOR_EVENT MI_INSTR(0x03, 0)
#define MI_ARB_CHECK MI_INSTR(0x05, 0)
#define MI_REPORT_HEAD MI_INSTR(0x07, 0)
#define MI_ARB_ON_OFF MI_INSTR(0x08, 0)
#define MI_BATCH_BUFFER_END MI_INSTR(0x0a, 0)
#define MI_SUSPEND_FLUSH MI_INSTR(0x0b, 0)
#define MI_OVERLAY_FLIP MI_INSTR(0x11, 0)
#define MI_SET_PREDICATE MI_INSTR(0x01, 0)
#define MI_ARB_CHECK MI_INSTR(0x05, 0)
#define MI_RS_CONTROL MI_INSTR(0x06, 0)
#define MI_URB_ATOMIC_ALLOC MI_INSTR(0x09, 0)
#define MI_PREDICATE MI_INSTR(0x0C, 0)
#define MI_RS_CONTEXT MI_INSTR(0x0F, 0)
#define MI_TOPOLOGY_FILTER MI_INSTR(0x0D, 0)
#define MI_LOAD_SCAN_LINES_EXCL MI_INSTR(0x13, 0)
#define MI_URB_CLEAR MI_INSTR(0x19, 0)
#define MI_UPDATE_GTT MI_INSTR(0x23, 0)
#define MI_CLFLUSH MI_INSTR(0x27, 0)
#define MI_REPORT_PERF_COUNT MI_INSTR(0x28, 0)
#define MI_LOAD_REGISTER_MEM MI_INSTR(0x29, 0)
#define MI_LOAD_REGISTER_REG MI_INSTR(0x2A, 0)
#define MI_RS_STORE_DATA_IMM MI_INSTR(0x2B, 0)
#define MI_LOAD_URB_MEM MI_INSTR(0x2C, 0)
#define MI_STORE_URB_MEM MI_INSTR(0x2D, 0)
#define MI_CONDITIONAL_BATCH_BUFFER_END MI_INSTR(0x36, 0)
#define MI_SEMAPHORE_MBOX MI_INSTR(0x16, 1) /* gen6+ */
#define MI_STORE_DWORD_IMM MI_INSTR(0x20, 1)
#define MI_STORE_DWORD_INDEX MI_INSTR(0x21, 1)
#define MI_SET_CONTEXT MI_INSTR(0x18, 0)
#define MI_LOAD_REGISTER_IMM(x) MI_INSTR(0x22, 2*(x)-1)
#define MI_STORE_REGISTER_MEM(x) MI_INSTR(0x24, 2*(x)-1)
#define MI_BATCH_BUFFER_START MI_INSTR(0x31, 0)
#define MI_FLUSH MI_INSTR(0x04, 0)
#define MI_DISPLAY_FLIP MI_INSTR(0x14, 2)
#define MI_LOAD_SCAN_LINES_INCL MI_INSTR(0x12, 0)
#define GFX_OP_PIPE_CONTROL(len) ((0x3<<29)|(0x3<<27)|(0x2<<24)|(len-2))
#define PIPELINE_SELECT ((0x3<<29)|(0x1<<27)|(0x1<<24)|(0x4<<16))
#define GFX_OP_3DSTATE_VF_STATISTICS ((0x3<<29)|(0x1<<27)|(0x0<<24)|(0xB<<16))
#define MEDIA_VFE_STATE ((0x3<<29)|(0x2<<27)|(0x0<<24)|(0x0<<16))
#define MEDIA_VFE_STATE_MMIO_ACCESS_MASK (0x18)
#define GPGPU_OBJECT ((0x3<<29)|(0x2<<27)|(0x1<<24)|(0x4<<16))
#define GPGPU_WALKER ((0x3<<29)|(0x2<<27)|(0x1<<24)|(0x5<<16))
#define GFX_OP_3DSTATE_DX9_CONSTANTF_VS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x39<<16))
#define GFX_OP_3DSTATE_DX9_CONSTANTF_PS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x3A<<16))
#define GFX_OP_3DSTATE_SO_DECL_LIST \
((0x3<<29)|(0x3<<27)|(0x1<<24)|(0x17<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_VS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x43<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_GS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x44<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_HS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x45<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_DS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x46<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_PS \
((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x47<<16))
#define MFX_WAIT ((0x3<<29)|(0x1<<27)|(0x0<<16))
#define COLOR_BLT ((0x2<<29)|(0x40<<22))
#define SRC_COPY_BLT ((0x2<<29)|(0x43<<22))
uint32_t opcodes[] = {
MI_NOOP,
MI_USER_INTERRUPT,
MI_WAIT_FOR_EVENT,
MI_ARB_CHECK,
MI_REPORT_HEAD,
MI_SUSPEND_FLUSH,
MI_SEMAPHORE_MBOX,
MI_STORE_DWORD_INDEX,
MI_LOAD_REGISTER_IMM(1),
MI_STORE_REGISTER_MEM(1),
MI_LOAD_REGISTER_MEM,
MI_BATCH_BUFFER_START,
MI_FLUSH,
MI_ARB_ON_OFF,
MI_PREDICATE,
MI_TOPOLOGY_FILTER,
MI_DISPLAY_FLIP,
MI_SET_CONTEXT,
MI_URB_CLEAR,
MI_STORE_DWORD_IMM,
MI_UPDATE_GTT,
MI_CLFLUSH,
MI_REPORT_PERF_COUNT,
MI_CONDITIONAL_BATCH_BUFFER_END,
GFX_OP_3DSTATE_VF_STATISTICS,
PIPELINE_SELECT,
MEDIA_VFE_STATE,
GPGPU_OBJECT,
GPGPU_WALKER,
GFX_OP_3DSTATE_SO_DECL_LIST,
GFX_OP_PIPE_CONTROL(5),
MI_LOAD_SCAN_LINES_INCL,
MI_LOAD_SCAN_LINES_EXCL,
MI_LOAD_REGISTER_REG,
MI_RS_STORE_DATA_IMM,
MI_LOAD_URB_MEM,
MI_STORE_URB_MEM,
GFX_OP_3DSTATE_DX9_CONSTANTF_VS,
GFX_OP_3DSTATE_DX9_CONSTANTF_PS,
GFX_OP_3DSTATE_BINDING_TABLE_EDIT_VS,
GFX_OP_3DSTATE_BINDING_TABLE_EDIT_GS,
GFX_OP_3DSTATE_BINDING_TABLE_EDIT_HS,
GFX_OP_3DSTATE_BINDING_TABLE_EDIT_DS,
GFX_OP_3DSTATE_BINDING_TABLE_EDIT_PS,
};
#define STD_MI_OPCODE_MASK 0xFF800000
#define STD_3D_OPCODE_MASK 0xFFFF0000
#define STD_2D_OPCODE_MASK 0xFFC00000
#define STD_MFX_OPCODE_MASK 0xFFFF0000
#define CMD_HASH_MASK STD_MI_OPCODE_MASK
/* small adjustments to _a_ to make values distinct */
static uint8_t mph_tab[] = {
0,0,10,0,51,0,34,0,12,22,0,0,28,0,9,0,
9,0,19,0,0,0,11,0,10,61,20,50,49,60,45,55,
};
/* The hash function */
static uint32_t mph_hash(uint32_t val)
{
uint32_t a, b, rsl;
val += 0xa195a44b;
val += (val << 8);
val ^= (val >> 4);
b = (val >> 18) & 0x1f;
a = val >> 27;
rsl = (a^mph_tab[b]);
return rsl;
}
int main(void)
{
int i;
for (i = 0; i < ARRAY_SIZE(opcodes); i++)
printf("%08x %d\n", opcodes[i] & 0xffff0000,
mph_hash(opcodes[i] & 0xffff0000));
return 0;
}
_______________________________________________
Intel-gfx mailing list
Intel-gfx@xxxxxxxxxxxxxxxxxxxxx
http://lists.freedesktop.org/mailman/listinfo/intel-gfx
