请选择 进入手机版 | 继续访问电脑版

 找回密码
 点一下
查看: 8833|回复: 9

模拟StringHash

[复制链接]
发表于 2010-12-24 07:19:52 | 显示全部楼层 |阅读模式
有人问到这个问题,很遗憾我现在才看到,隔的时间太长了,还是另开一贴吧。
http://bbs.islga.org/read-htm-tid-37234.html

[jass]
globals
    integer array udg_C2
    integer udg_Ah
    integer udg_Al
    integer udg_Bh
    integer udg_Bl
    integer udg_Ch
    integer udg_Cl
    integer udg_Rh
    integer udg_Rl
endglobals

function SH_S2I takes string s returns integer
    //这个函数好像发不出来
endfunction

function SH_StringChar takes string s, integer n returns integer
    local string ss = SubString(s, n, n+1)
    
    if (ss == "/") then
        set ss = "\\"
    endif

    return SH_S2I(ss)
endfunction

function SH_XOR takes integer x, integer y returns integer
    local integer z = 0
    local integer i = 0

    loop
        exitwhen (i == 16)
        if ((x - x/2*2) != (y - y/2*2)) then
            set z = z + udg_C2
        endif
        set x = x / 2
        set y = y / 2
        set i = i + 1    
    endloop

    return z
endfunction

function SH_NOT takes integer x returns integer
    local integer z = 0
    local integer i = 0

    loop
        exitwhen (i == 16)
        if ((x - x/2*2) == 0) then
            set z = z + udg_C2
        endif
        set x = x / 2
        set i = i + 1    
    endloop

    return z
endfunction

function SH_LShift takes integer Ah, integer Al, integer n returns nothing
    if (n > 8) then
        call SH_LShift(Ah, Al, n - 8)
        call SH_LShift(udg_Rh, udg_Rl, 8)
        return
    endif
    set udg_Rh = Ah * udg_C2[n]
    set udg_Rl = Al * udg_C2[n]
    set udg_Rh = udg_Rh + udg_Rl / udg_C2[16]
    set udg_Rl = udg_Rl - udg_Rl / udg_C2[16] * udg_C2[16]
    set udg_Rh = udg_Rh - udg_Rh / udg_C2[16] * udg_C2[16]
endfunction

function SH_RShift takes integer Ah, integer Al, integer n returns nothing
    if (n > 8) then
        call SH_RShift(Ah, Al, n - 8)
        call SH_RShift(udg_Rh, udg_Rl, 8)
        return
    endif
    set udg_Rh = Ah/udg_C2[n]
    set udg_Rl = Al/udg_C2[n] + (Ah - udg_Rh*udg_C2[n])*udg_C2[16-n]
endfunction

function SH_ADD_A takes integer Xh, integer Xl returns nothing
    set udg_Ah = udg_Ah + Xh
    set udg_Al = udg_Al + Xl

    if (udg_Al > udg_C2[16]) then
        set udg_Al = udg_Al - udg_C2[16]
        set udg_Ah = udg_Ah + 1
&#160;&#160;&#160;&#160;elseif (udg_Al < 0) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Al = udg_Al + udg_C2[16]
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ah = udg_Ah - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (udg_Ah > udg_C2[16]) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ah = udg_Ah - udg_C2[16]
&#160;&#160;&#160;&#160;elseif (udg_Ah < 0) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ah = udg_Ah + udg_C2[16]
&#160;&#160;&#160;&#160;endif
endfunction

function SH_ADD_B takes integer Xh, integer Xl returns nothing
&#160;&#160;&#160;&#160;set udg_Bh = udg_Bh + Xh
&#160;&#160;&#160;&#160;set udg_Bl = udg_Bl + Xl
&#160;&#160;&#160;&#160;if (udg_Bl > udg_C2[16]) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Bl = udg_Bl - udg_C2[16]
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Bh = udg_Bh + 1
&#160;&#160;&#160;&#160;elseif (udg_Bl < 0) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Bl = udg_Bl + udg_C2[16]
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Bh = udg_Bh - 1&#160;&#160;
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (udg_Bh > udg_C2[16]) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Bh = udg_Bh - udg_C2[16]
&#160;&#160;&#160;&#160;elseif (udg_Bh < 0) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Bh = udg_Bh + udg_C2[16]
&#160;&#160;&#160;&#160;endif
endfunction

function SH_ADD_C takes integer Xh, integer Xl returns nothing
&#160;&#160;&#160;&#160;set udg_Ch = udg_Ch + Xh
&#160;&#160;&#160;&#160;set udg_Cl = udg_Cl + Xl
&#160;&#160;&#160;&#160;if (udg_Cl > udg_C2[16]) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Cl = udg_Cl - udg_C2[16]
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ch = udg_Ch + 1
&#160;&#160;&#160;&#160;elseif (udg_Cl < 0) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Cl = udg_Cl + udg_C2[16]
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ch = udg_Ch - 1&#160;&#160;
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (udg_Ch > udg_C2[16]) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ch = udg_Ch - udg_C2[16]
&#160;&#160;&#160;&#160;elseif (udg_Ch < 0) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_Ch = udg_Ch + udg_C2[16]
&#160;&#160;&#160;&#160;endif
endfunction

function SH_T2 takes integer a, integer b, integer c returns nothing
&#160;&#160;&#160;&#160;call SH_RShift(udg_Ch, udg_Cl, a)
&#160;&#160;&#160;&#160;call SH_ADD_A(-udg_Bh, -udg_Bl)
&#160;&#160;&#160;&#160;call SH_ADD_A(-udg_Ch, -udg_Cl)
&#160;&#160;&#160;&#160;set udg_Ah = SH_XOR(udg_Ah, udg_Rh)
&#160;&#160;&#160;&#160;set udg_Al = SH_XOR(udg_Al, udg_Rl)

&#160;&#160;&#160;&#160;call SH_LShift(udg_Ah, udg_Al, b)
&#160;&#160;&#160;&#160;call SH_ADD_B(-udg_Ch, -udg_Cl)
&#160;&#160;&#160;&#160;call SH_ADD_B(-udg_Ah, -udg_Al)
&#160;&#160;&#160;&#160;set udg_Bh = SH_XOR(udg_Bh, udg_Rh)
&#160;&#160;&#160;&#160;set udg_Bl = SH_XOR(udg_Bl, udg_Rl)

&#160;&#160;&#160;&#160;call SH_RShift(udg_Bh, udg_Bl, c)
&#160;&#160;&#160;&#160;call SH_ADD_C(-udg_Ah, -udg_Al)
&#160;&#160;&#160;&#160;call SH_ADD_C(-udg_Bh, -udg_Bl)
&#160;&#160;&#160;&#160;set udg_Ch = SH_XOR(udg_Ch, udg_Rh)
&#160;&#160;&#160;&#160;set udg_Cl = SH_XOR(udg_Cl, udg_Rl)
endfunction

function SH_T1 takes nothing returns nothing
&#160;&#160;&#160;&#160;call SH_T2(13,&#160;&#160;8, 13)
&#160;&#160;&#160;&#160;call SH_T2(12, 16,&#160;&#160;5)
&#160;&#160;&#160;&#160;call SH_T2( 3, 10, 15)
endfunction

function SH_Convert takes integer Xh, integer Xl returns integer
&#160;&#160;&#160;&#160;if (Xh >= udg_C2[15]) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set Xh = SH_NOT(Xh)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set Xl = SH_NOT(Xl)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set Xl = Xl + 1
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set Xh = Xh*udg_C2[16]+Xl
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set Xh = -Xh
&#160;&#160;&#160;&#160;else
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set Xh = Xh*udg_C2[16]+Xl
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;return Xh
endfunction

function SH_StringHashEx takes string s, integer len returns integer
&#160;&#160;&#160;&#160;local integer n = 0
&#160;&#160;&#160;&#160;local integer size_t = len

&#160;&#160;&#160;&#160;set udg_Ah = $9E37
&#160;&#160;&#160;&#160;set udg_Al = $79B9
&#160;&#160;&#160;&#160;set udg_Bh = $9E37
&#160;&#160;&#160;&#160;set udg_Bl = $79B9
&#160;&#160;&#160;&#160;set udg_Ch = 0
&#160;&#160;&#160;&#160;set udg_Cl = 0

&#160;&#160;&#160;&#160;loop
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;exitwhen len < 12
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_A(SH_StringChar(s, n+3)*256+SH_StringChar(s, n+2), SH_StringChar(s, n+1)*256+SH_StringChar(s, n))
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_B(SH_StringChar(s, n+7)*256+SH_StringChar(s, n+6), SH_StringChar(s, n+5)*256+SH_StringChar(s, n+4))
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_C(SH_StringChar(s, n+11)*256+SH_StringChar(s, n+10), SH_StringChar(s, n+9)*256+SH_StringChar(s, n+8))
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_T1()
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set n = n + 12
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 12
&#160;&#160;&#160;&#160;endloop

&#160;&#160;&#160;&#160;call SH_ADD_C(0, size_t)

&#160;&#160;&#160;&#160;if (len == 11) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_C(SH_StringChar(s, n+10)*256, 0)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 10) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_C(SH_StringChar(s, n+9), 0)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 9) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_C(0, SH_StringChar(s, n+8)*256)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 8) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_B(SH_StringChar(s, n+7)*256, 0)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 7) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_B(SH_StringChar(s, n+6), 0)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 6) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_B(0, SH_StringChar(s, n+5)*256)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 5) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_B(0, SH_StringChar(s, n+4))
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 4) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_A(SH_StringChar(s, n+3)*256, 0)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 3) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_A(SH_StringChar(s, n+2), 0)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 2) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_A(0, SH_StringChar(s, n+1)*256)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif
&#160;&#160;&#160;&#160;if (len == 1) then
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;call SH_ADD_A(0, SH_StringChar(s, n))
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set len = len - 1
&#160;&#160;&#160;&#160;endif

&#160;&#160;&#160;&#160;call SH_T1()

&#160;&#160;&#160;&#160;return SH_Convert(udg_Ch, udg_Cl)
endfunction

function SH_StringHash takes string s returns integer
&#160;&#160;&#160;&#160;return SH_StringHashEx(StringCase(s, true), StringLength(s))
endfunction

function SH_Init takes nothing returns nothing
&#160;&#160;&#160;&#160;local integer i = 1
&#160;&#160;&#160;&#160;set udg_C2[0] = 1
&#160;&#160;&#160;&#160;loop
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;exitwhen (i == 31)
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set udg_C2 = udg_C2[i-1]*2
&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;set i = i + 1
&#160;&#160;&#160;&#160;endloop
endfunction
[/jass]

比较麻烦的是,jass的整数运算不支持无符号整数的运算,一开始想用有符号整数来模拟无符号整数,但还是太麻烦了。现在是用两个整数来模拟一个无符号整数,大部分代码都是浪费在这个上面。

StringHash.w3x

21 KB, 下载次数: 231

评分

参与人数 1威望 +2 收起 理由
疯人¢衰人 + 2 之前点错

查看全部评分

发表于 2010-12-24 07:48:41 | 显示全部楼层
为啥非要用无符号数呢
回复

使用道具 举报

 楼主| 发表于 2010-12-24 08:02:53 | 显示全部楼层
引用第1楼疯人¢衰人于2010-12-24 07:48发表的  :
为啥非要用无符号数呢

blz实现这个函数就是用无符号整数的,不用就无法得到正确的结果
回复

使用道具 举报

 楼主| 发表于 2010-12-24 15:57:36 | 显示全部楼层
作用嘛,我研究这个的起因是为了把某张图弄成1.24和1.20兼容,那个图有记录码,记录码的生产算法里用到了StringHash。
回复

使用道具 举报

发表于 2010-12-24 17:45:32 | 显示全部楼层
StringCase是转换大小写?
回复

使用道具 举报

 楼主| 发表于 2010-12-24 18:29:43 | 显示全部楼层
引用第4楼Conflux于2010-12-24 17:45发表的  :
StringCase是转换大小写?

是,StringHash是无视字母大小写的
回复

使用道具 举报

发表于 2011-2-17 10:02:18 | 显示全部楼层
好东西,先收藏~
回复

使用道具 举报

发表于 2011-8-30 15:40:09 | 显示全部楼层
原来act大神这么久之前就在这里有这个帖子了...
回复

使用道具 举报

发表于 2013-8-27 10:54:50 | 显示全部楼层
厉害

点评

挖坟了····  发表于 2013-8-28 08:27
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 点一下

本版积分规则

Archiver|移动端|小黑屋|地精研究院

GMT+8, 2024-3-29 10:08 , Processed in 0.248161 second(s), 26 queries .

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表