本案是关于数据压缩技术，特别有关于滑动窗口压缩。
背景技术：
：：基于哈希的滑动窗口压缩技术中往往会以一哈希表结构储存位于滑动窗口中的一定数量(例如，2kb、4kb或32kb)的历史数据的哈希键及其地址，供匹配比对参考，以获得哈希匹配结果(如，哈希键相符)。然后根据哈希匹配结果进行进一步的匹配(如，相符长度)，以将原始数据串中的部分数据串以匹配数据(包括例如距离、匹配长度)取代，以达到数据压缩效果。历史数据的哈希键及其地址的储存需要相当空间。如何节省历史数据的哈希键及其地址的储存空间，为本
技术领域：
：一项重要课题。技术实现要素：本案为滑动窗口压缩提出一种历史数据的哈希表储存结构，精简储存历史数据。滑动窗口压缩常使用哈希(hash)运算。本案提出哈希运算的哈希表中的哈希行(hashline)储存格式。根据本案一种实施方式实现的一数据压缩器包括一哈希运算硬件以及一储存器。该哈希运算硬件被配置为根据取自一原始数据串的一输入哈希键(currenthashkey)产生一哈希值(hashvalue)，自一哈希表(hashtable)取得对应该哈希值的一哈希行，比对该哈希行的多个储存格(entries)，寻找对应该输入哈希键的至少一匹配哈希键(matchedhashkey)。该储存器储存该哈希表。该哈希行包括一前缀(prefix)地址栏，储存一前缀地址(prefixaddress)。该哈希行的所述储存格各自载有一哈希键(hashkey)以及一偏移量(offset)。该哈希运算硬件根据该前缀地址及所述匹配哈希键的该偏移量得到所述匹配哈希键的地址(address)。一种实施方式中，该哈希运算硬件根据该前缀地址及各偏移量得到所述储存格各自对应的哈希键的地址，并将所述对应的哈希键的地址与该输入哈希键的地址超过一滑动窗口范围的储存格设定为无效。一种实施方式中，该哈希运算硬件根据该前缀地址判断所述储存格既有储存的哈希键的地址是否都超过一滑动窗口范围，如果所述储存格既有储存的哈希键的地址都超过一滑动窗口范围，将所述储存格设定为无效。一种实施方式中，该哈希运算硬件选择该哈希行的所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入。一种实施方式中，该哈希行的所述储存格内容若都为有效，该哈希运算硬件释出所述储存格之一将储存该输入哈希键、以及该输入哈希键的偏移量存入。所释出的储存格所载哈希键的地址与该输入哈希键的地址相距最远。一种实施方式中，该哈希行包括一有效标示栏，该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否。一种实施方式中，该前缀地址以及该偏移量间有一重叠比特。一种实施方式中，该前缀地址为prefix[(n-1):(m-1)]。n以及m为数值。m小于n。上述偏移量为offset[(m-1):0]。prefix[m-1]以及offset[m-1]即上述重叠比特(bit)。一种实施方式中，该哈希运算硬件根据{prefix[(n-1):(m-1)],(m-1)’b0} offset[(m-1):0]得到所对应的哈希键的地址，其中，(m-1)’b0表示m-1个二进制0。一种实施方式中，n为32，m为16。该输入哈希键的地址为cur_addr[31:0]。该前缀地址的一旧版数值为prefix_old[31:15]。上述储存格既有储存的偏移量为offset_old[15:0]。该哈希运算硬件将cur_addr[31:16]减去prefix_old[31:16]，获得的数值为d。该哈希运算硬件更判读prefix_old[15]以及cur_addr[15]。d大于1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，并更新该有效标示栏以标示所述储存格既有储存的内容无效。d大于1时，该哈希运算硬件更以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。d为1、prefix_old[15]为0、且cur_addr[15]为0时，该哈希运算硬件以{prefix_old[31:16],1’b1}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，且以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量存入该哈希表。d为1、prefix_old[15]为1、且cur_addr[15]为0时，该哈希运算硬件以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量存入该哈希表。d为1、prefix_old[15]为0、且cur_addr[15]为1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，更新该有效标示栏，标示所述储存格既有储存的内容无效，并以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。d为1、prefix_old[15]为1、且cur_addr[15]为1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，并以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。d为0且prefix_old[15]为0时，该哈希运算硬件以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。前述哈希运算硬件可以其他结构实现。采用前述哈希行储存格式的数据压缩方法也属于本案应用。根据本案一种实施方式实现的一种数据压缩方法包括：根据取自一原始数据串的一输入哈希键产生一哈希值；自一哈希表取得对应该哈希值的一哈希行，其中，该哈希行包括一前缀地址栏，储存一前缀地址；比对该哈希行的多个储存格，寻找对应该输入哈希键的至少一匹配哈希键，其中，该哈希行的所述储存格各自载有一哈希键以及一偏移量；及根据该前缀地址及所述匹配哈希键的该偏移量得到所述匹配哈希键的地址。本发明中，哈希表的每一哈希行中包含一个前缀地址栏和多个储存格，每个储存格用于储存一个哈希键及其地址的偏移量，而前缀地址栏用于储存同一哈希行中各个哈希键共用的前缀地址。由于只使用一个前缀地址栏就可以储存同一哈希行中所有哈希键共用的前缀地址，因而不需要分别为各个哈希键的前缀地址单独分配储存空间，从而节省了用于储存历史数据的哈希键及其地址的储存空间。下文特举实施例，并配合附图，详细说明本
发明内容。附图说明图1示出一异构计算平台(heterogeneouscomputingplatform)100；图2为根据本案一种实施方式示出一数据压缩器200；图3举例说明该数据压缩器200使用到的哈希运算；图4根据本案一种实施方式示出一哈希行的储存格式400；图5示出前缀地址prefix[31:15]以及偏移量offset[15:0]，两者有一比特([15])重叠；图6a以及图6b显示32kb滑动窗口的跨界状况；图7示出一表格700，显示本案一种实施方式所实现的哈希运算硬件如何对应数值d、prefix_old[15]以及cur_addr[15]动作；图8示出哈希表的维护流程。具体实施方式以下叙述列举本发明的多种实施例。以下叙述介绍本发明的基本概念，且并非意图限制本
发明内容。实际发明范围应依照权利要求界定。图1示出一异构计算平台(heterogeneouscomputingplatform)100，整合多核运算单元(包括核心#0、核心#1、核心#2…)以及各类加速器(加速器#0…加速器#n)。各加速器根据多核运算单元下达的指令动作，且是透过特定通讯界面及末级快取(llc,lastlevelcache)存取数据。本案一种实施方式是为数据压缩需求实现一加速器，整合于如图1所示的异构计算平台100。图2为根据本案一种实施方式示出一数据压缩器200。数据压缩器200可作为前述加速器，也可应用于其他计算架构。图2以方块图示意该数据压缩器200的硬件功能。所述硬件可以逻辑门实现，也可以软硬体共同设计方式实现。预取自一原始数据串p的数据集合成一哈希键(hashkey，如，3字节)，输入一哈希值运算方块202求得哈希值(hashvalue)。哈希值相同的历史哈希键(载于对应该哈希值的一哈希行)自一哈希表储存器204取出，与输入哈希键以一哈希键比较方块206进行比较。若有匹配(即与输入哈希键相同)者，则所有的匹配哈希键及其各自的地址均会被取出。然后，根据各个匹配哈希键及其地址和一滑动窗口储存器208的储存内容(例如，32kb的历史数据)，一最大长度辨识(longestmatch)方块210辨识原始数据串p中以输入哈希键开始的数据串在滑动窗口储存器208的储存内容中所能匹配的最大长度(例如各个匹配哈希键开始的历史内容)，并根据所能匹配的最大长度生成匹配数据。匹配数据(包括距离、长度)缓存于一匹配结果缓存器212，其中“长度”是各个匹配哈希键开始的历史内容中与原始数据串p中以输入的哈希键开始的数据串能匹配的最大长度中的最长者。排序逻辑(retirelogic)214对无匹配的数据原文216与匹配结果缓存器212的内容进行排序，使符合原始数据串p顺序后，交由编码器218编码(例如，基于lz77算法的deflate、lz4、lzo、lzs)。如此一来，重复出现的数据简化由匹配数据(包括距离、长度)取代，达压缩效果。编码结果缓存于压缩数据缓存器220，再经接口222输出。至于哈希表更新方块224以及哈希表管理方块226，说明如下。根据哈希值运算方块202对输入哈希键运算出的哈希值，哈希表更新方块224择定哈希行(hashline)进行更新，该输入哈希键以及该输入哈希键的地址资讯存入择定的哈希行。哈希表管理方块226将更新后的该哈希行存回该哈希表储存器204。哈希表储存器204因而储存有滑动窗口内的历史哈希键，供该哈希键比较方块206进行比对时使用。本案是以特殊的哈希行储存格式进行哈希表管理(226)，并相应发展出哈希表更新技术(224)。以下还举例说明哈希运算硬件(包括方块202、206、224以及226)以及哈希表储存器204的运作方式。图3举例说明该数据压缩器200使用到的哈希运算。原始数据串p为’abcdefgcde’。每三个字节组成一个哈希键(hashkey)，对应一哈希值(hashvalue)。每个哈希键具有一地址，哈希键的地址为哈希键在原始数据串中的地址。例如,哈希键’abc’的地址为0，哈希键’bcd’的地址为1，以此类推。根据该哈希值，哈希表(hashtable)的一哈希行(hashline)被选出，然后进行哈希键比对(206)以及哈希表更新(224与226)，并且输出所有匹配哈希键及其各自的地址。表格300条列哈希表的更新。例如，哈希值为0的哈希键’abc’及其地址0存入哈希行line0的储存格line0[0]，在图3中以’abc’(0)表示哈希键’abc’及其地址0；以此类推。哈希表储存器204储存的哈希行line0…line7内容如图示。图示中，由于地址为2、3以及7的哈希键经哈希值运算方块202进行哈希运算后得到相同的哈希值3，则地址为2的哈希键及其地址’cde’(2)、地址为3的哈希键及其地址’def’(3)、以及地址为7的哈希键及其地址’cde’(7)都存入哈希行line3，且是分别存入储存格line3[0]、line3[1]以及line3[2]。值得注意的是，在将地址为3的哈希键及其地址’def’(3)存入哈希行line3前，先将哈希键’def’与哈希行line3中已存储的所有哈希键比对(假设此时哈希行line3中只有储存格line3[0]中储存着哈希键’cde’)，确定哈希键’def’与地址为2的哈希键’cde’并不匹配，则哈希键’def’中的字节’d’将被直接输出，即不会进行压缩编码。再举例而言，在将地址为7的哈希键及其地址’cde’(7)存入哈希行line3前，先将哈希键’cde’与哈希行中已存储的所有哈希键比对(假设此时哈希行line3中只有储存格line3[0]以及line3[1]储存着哈希键’cde’以及’def’)，辨识出地址为7的哈希键’cde’与地址为3的哈希键’def’不匹配，但与地址为2的哈希键’cde’匹配，则匹配哈希键及其地址’cde’(2)将被发送给最大长度辨识方块210做进一步匹配，寻出匹配长度。最大长度辨识方块210可采习知的各种最大长度匹配技术，在此不再赘述。本案特别是对哈希行的储存格式进行特殊设计，无须过多比特数即可储存各储存格的哈希键及其对应的地址。图4根据本案一种实施方式示出一哈希行的储存格式400，其中包括八个储存格entry_0…entry_7。该哈希行包括一有效标示栏402，该有效标示栏更细分为多个栏位以分别标示所述储存格entry_0…entry_7各自有效与否。具体而言，该有效标示栏402以八个比特对应标示八个储存格entry_0…entry_7有效与否。在一实施例中，有效标示栏402中的比特为1表示对应储存格有效，为0表示对应储存格无效。而在另一实施例中，有效标示栏402中的比特为0表示对应储存格有效，为1表示对应储存格无效。在后文中，将以有效标示栏402中的比特为1表示对应储存格有效，为0表示对应储存格无效为例进行描述。各储存格储存一哈希键以及一偏移量。前缀地址(prefixaddress)栏404填写一前缀地址，用来与各储存格(entry_0…entry_7)所载的上述偏移量结合，成为地址addr，显示哈希键对应该原始数据串p哪个位置。也即是说，哈希运算硬件可根据前缀地址(prefixaddress)栏404及各储存格(entry_0…entry_7)所载的各哈希键的偏移量得到各个哈希键的完整地址addr。值得注意的是，本领域技术人员可依据设计需求改变哈希行中储存格的数量，并相应改变有效标示栏的栏位数量(比如，将有效标示栏的栏位数量设置为哈希行中储存格的数量)，以储存更多或更少的哈希键及其对应的偏移量。一种实施方式中，滑动窗口大小为32kb(kilobyte，千字节)，哈希键长度为3b(byte，字节)。原始数据串p可达4g长度，地址addr以32比特表示。如图4的标示，前缀地址(404)为17比特的数值prefix[31:15]。各储存格载有3b的哈希键以及16比特的偏移量offset[15:0]。储存格式400只使用了145比特(17 8*16)即成功记载8个哈希键的地址资讯。相较之，传统技术每一个储存格储存的并非偏移量，而是完整的32比特地址addr[31:0]。传统一哈希行需要256比特才能记载8个哈希键的地址资讯。显然本案提出的储存格式400较节省储存空间(可节省43％((256-145)/256)的储存空间)。哈希表储存器204尺寸无须过大，有效减少数据压缩器200的成本。图5示出前缀地址prefix[31:15]以及偏移量offset[15:0]，两者有一比特([15])重叠。前缀地址prefix[31:15]以及偏移量offset[15:0]组合后，须组成地址addr[31:0]。实现方式是：随着填入哈希键，哈希运算硬件动态调整对应的哈希行储存的前缀地址prefix[31:15]、以及各储存格(entry_0…entry_7)所载的偏移量offset[15:0]，使得以下运算成立：addr[31:0]＝{prefix[31:15],15’b0} offset[15:0]其中，15’b0表示15个二进制0，{prefix[31:15],15’b0}表示一个[31:0]的二进制数字；这个二进制数字的[31:15]的值为prefix[31:15]，这个二进制数字的[14:0]的每个比特的值为0。即是说，通过上述运算，哈希运算硬件可根据前缀地址prefix[31:15]及各储存格(entry_0…entry_7)所载的各哈希键的偏移量offset[15:0]得到各个哈希键的完整地址addr。如此储存格式400特别需要考虑滑动窗口的跨界状况。图6a以及图6b显示32kb滑动窗口的跨界状况。原始数据串中各字节(byte)的地址addr是从0开始依次增加的。举例来说，如图3所示，原始数据串(p)’abcdefgcde’中各字节的地址依次为0，1，2，3，4，5，6，7，8，9。以32kb为单位将原始数据串的地址分为多个段(每个段称为一个32k段)，则任意相邻的32kb段的地址addr的比特addr[15]的值都不同。例如，地址addr小于32kb(即位于第一32k段)的所有字节的地址addr的比特addr[15]的值都为[0]2([]2表示[]中为二进制数字，下同)，地址addr大于或等于32kb并且地址addr小于64kb(即位于第二32k段)的所有字节的地址addr的比特addr[15]的值都为[1]2，依此类推。如果以64kb为单位将原始数据串的地址分为多个段，则任意相邻段的地址addr的高位部分addr[31:16]相差1。例如，原始数据串中地址addr小于64kb的所有字节的高位部分addr[31:16]的值(以下称作第一64k段高位值)为[0]16([]16表示[]中为十六进制数字，下同)，地址addr大于或等于64kb并且地址addr小于128kb的所有字节的高位部分addr[31:16]的值(以下称作第二64k段高位值)为[1]16，地址addr大于或等于128kb并且地址addr小于194kb的所有字节的高位部分addr[31:16]的值(以下称作第三64k段高位值)为[2]16，依此类推。可见，第一64k段高位值([0]16)比第二64k段高位值([1]16)小1，第二64k段高位值([1]16)比第三64k段高位值([2]16)小1；即，第二64k段高位值([1]16)比第一64k段高位值([0]16)大1，第三64k段高位值([2]16)比第二64k段高位值([1]16)大1。另外，第一32k段和第二32k段组成第一64k段，第三32k段和第四32k段组成第二64k段，以此类推。图6a和图6b中示出了以多个32k段(以从左向右的顺序，每两个32k段组成一个64k段)显示的原始数据串的地址空间，与地址空间部分重叠的长方形表示32kb滑动窗口(32kb滑动窗口覆盖连续的32kb地址空间)。对原始数据串进行压缩的过程中，32kb滑动窗口从原始数据串的地址空间的第一32k段开始连续向右滑动，每次向右滑动一个字节，直至整个原始数据串中的数据都被压缩完为止。图6a中所示的哈希键key1和key2位于32kb滑动窗口中，其中哈希键key1位于第一32k段、哈希键key2位于第二32k段，所以哈希键key1和key2跨越了地址空间的32k边界。图6b中所示的哈希键key3和key4位于32kb滑动窗口中，其中哈希键key3位于第一64k段、哈希键key4位于第二64k段，所以哈希键key3和key4跨越了地址空间的64k边界。一哈希行所载的前缀地址prefix[31:15]以及其中各储存格(entry_0…entry_7)所载的偏移量offset[15:0]需要能应付地址addr每32kb以及每64kb的变化。图6a以哈希键key1和key2为例，说明将跨越地址空间的32kb边界的哈希键存入到同一个哈希行时如何设置哈希行的前缀地址prefix[31:15]以及与每个哈希键对应的偏移量offset[15:0]。假设哈希键key1和key2经过哈希值运算方块202计算之后得到相同的哈希值，则哈希键key1和key2将被存入同一个哈希行。例如，图3中的哈希键’cde’和’def’的哈希值都为3，所以哈希键’cde’和’def’都被储存到哈希行line3中。由于同一个哈希行只为所有哈希键储存一个共用的前缀地址prefix[31:15]，因此需要将哈希键key1和key2的地址分别分割为前缀地址prefix[31:15]和偏移量offset[15:0]两部分，并且需要将哈希键key1和key2的前缀地址设置为相同的值。如图6a所示，哈希键key1位于第一32k段内，其地址addr[31:0]为[0000，0000，0000，0000，0000，0000，0000，1110]2，即其地址高位部分addr[31:16]为[0000，0000，0000，0000]2、其地址的比特addr[15]为[0]2、其地址低位部分addr[14:0]为[000，0000，0000，1110]2。哈希键key2位于第二32k段内，其地址addr[31:0]为[0000，0000，0000，0000，1000，0000，0000，0011]2，即其地址高位部分addr[31:16]为[0000，0000，0000，0000]2、其地址的比特addr[15]为[1]2、其地址低位部分addr[14:0]为[000，0000，0000，0011]2。因此可以将哈希键key1和key2共用的前缀地址prefix[31:15]设置为[0000，0000，0000，0000,0]2。相应地，为哈希键key1填写的偏移量offset[15:0]为[0000，0000，0000，1110]2，且为哈希键key2填写的偏移量offset[15:0]为[1000，0000，0000，0011]2。如此一来，哈希键key1对应的地址[0000，0000，0000，0000，0000，0000，0000，1110]2、哈希键key2对应的地址[0000，0000，0000，0000，1000，0000，0000，0011]2都可通过{prefix[31:15],15’b0} offset[15:0]正确得出。例如，对于哈希键key1来说，{prefix[31:15],15’b0}为[0000，0000，0000，0000,0000，0000，0000，0000]2，offset[15:0]为[0000，0000，0000，1110]2，所以哈希运算硬件可通过公式{prefix[31:15],15’b0} offset[15:0]得到其地址为[0000，0000，0000，0000,0000，0000，0000，1110]2。对于哈希键key2来说，{prefix[31:15],15’b0}为[0000，0000，0000，0000,0000，0000，0000，0000]2，offset[15:0]为[1000，0000，0000，0011]2，所以哈希运算硬件可通过公式{prefix[31:15],15’b0} offset[15:0]得到其地址为[0000，0000，0000，0000,1000，0000，0000，0011]2。滑动视窗跨32kb切换点的状况被正确应付。图6b以哈希键key3和key4为例，说明将跨越地址空间的64kb边界的哈希键储存到同一个哈希行时如何设置哈希行的前缀地址prefix[31:15]以及与每个哈希键对应的偏移量offset[15:0]。假设哈希键key3和key4经过哈希值运算方块202计算之后得到相同的哈希值，则哈希键key3和key4将被存入同一个哈希行。由于同一个哈希行只为所有哈希键储存一个共用的前缀地址prefix[31:15]，因此需要将哈希键key3和key4的地址分别分割为前缀地址prefix[31:15]和偏移量offset[15:0]两部分，并且需要将哈希键key3和key4的前缀地址设置为相同的值。如图6b所示，哈希键key3位于第一64k段内，其地址addr[31:0]为[0000，0000，0000，0000，1000，0000，0000，1110]2，即其地址高位部分addr[31:16]为[0000，0000，0000，0000]2、其地址的比特addr[15]为[1]2、其地址低位部分addr[14:0]为[000，0000，0000，1110]2。哈希键key4位于第二64k段内，其地址addr[31:0]为[0000，0000，0000，0001，0000，0000，0000，0011]2，即其地址高位部分addr[31:16]为[0000，0000，0000，0001]2、其地址的比特addr[15]为[0]2、其地址低位部分addr[14:0]为[000，0000，0000，0011]2。因此可以将哈希键key3和key4共用的前缀地址prefix[31:15]设置为[0000，0000，0000，0000,1]2。相应地，为哈希键key3填写的偏移量offset[15:0]为[0000，0000，0000，1110]2，且为哈希键key4填写的偏移量offset[15:0]为[1000，0000，0000，0011]2。如此一来，哈希键key3对应的地址[0000，0000，0000，0000，1000，0000，0000，1110]2、哈希键key4对应的地址[0000，0000，0000，0001，0000，0000，0000，0011]2都可通过公式{prefix[31:15],15’b0} offset[15:0]正确得出。例如，对于哈希键key3来说，{prefix[31:15],15’b0}为[0000，0000，0000，0000,1000，0000，0000，0000]2，offset[15:0]为[0000，0000，0000，1110]2，所以哈希运算硬件可通过公式{prefix[31:15],15’b0} offset[15:0]得到其地址为[0000，0000，0000，0000,1000，0000，0000，1110]2。对于哈希键key4来说，{prefix[31:15],15’b0}为[0000，0000，0000，0000,1000，0000，0000，0000]2，offset[15:0]为[1000，0000，0000，0011]2，所以哈希运算硬件可通过公式{prefix[31:15],15’b0} offset[15:0]得到其地址为[0000，0000，0000，0001,0000，0000，0000，0011]2。滑动视窗跨64kb切换点的状况被正确应付。前缀地址prefix[31:15]、以及各储存格(entry_0…entry_7)所载的偏移量offset[15:0]的填写以及维护可能有多种方式。一种实施方式中，一哈希键(输入哈希键)更新至一哈希行时，需要将该哈希键及其对应的地址存入该择定的哈希行，哈希运算硬件选择该哈希行的所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入。具体而言，哈希运算硬件进行哈希表更新(224与226)前会计算d(distance,距离)值(d＝cur_addr[31:16]-prefix_old[31:16])，且特别判断两个比特prefix_old[15]以及cur_addr[15]。cur_addr[31:16]为该输入哈希键的地址cur_addr[31:0]的高位部分。prefix_old[31:16]为前缀地址prefix[31:15]的旧版数值prefix_old[31:15](旧版数值即指更新之前的值)的高位部分。prefix_old[15]取自prefix_old[31:15]的重叠比特。cur_addr[15]取自cur_addr[31:0]的重叠比特。哈希运算硬件进行哈希表更新(224与226)时将基于此三个数值d、prefix_old[15]以及cur_addr[15]更新该哈希行所载的地址资讯。前缀地址prefix[31:15]由旧版数值prefix_old[31:15]更新为新值prefix_new[31:15]。既有储存格所载的旧版偏移量offset_old[15:0]更新为新值offset_new[15:0]。此刻填写的储存格则填入偏移量cur_offset[15:0]。现在描述在更新时如何在该哈希行中选择适当的储存格。通常，哈希运算硬件会选择一无效的储存格，至于一个存储既有哈希键的储存格是如何被设定为无效的，具体而言，该哈希运算硬件可根据该前缀地址prefix[31:15]及各偏移量offset_old[15:0]得到所述储存格各自既有哈希键的地址addr，并将既有哈希键的地址addr与该输入哈希键的地址超过一滑动窗口范围(例如32k)的储存格设定为无效。在另一实施例中，哈希运算硬件可仅仅简单地根据该哈希行的前缀地址prefix[31:15]判断所述储存格既有储存的哈希键的地址是否都超过一滑动窗口范围(即后面图7所述的判断“d是否大于1”，或者判断“d为1、prefix_old[15]为0、且cur_addr[15]为1”这三个条件是否同时成立)，藉此将该哈希行的所有储存格均设定为无效。如果该哈希行中所有的储存格均为有效，在一实例中，该哈希运算硬件会选择所载哈希键的地址与该输入哈希键的地址addr相距最远的储存格，并将其释出以存入该输入哈希键及其偏移量，下面图7会详述。至于如何根据该输入哈希键的地址更新该哈希行的前缀地址prefix[31:15]及其所有既有储存格所载的旧版偏移量offset_old[15:0]，并且计算其需要存入的该输入哈希键的偏移量cur_offset[15:0]，下面图7亦会详述。图7示出一表格700，显示本案一种实施方式所实现的哈希运算硬件如何对应数值d、prefix_old[15]以及cur_addr[15]动作。”无效”者须以有效标示栏402的相关比特标示(例如，改为”0”值)。如此硬件功能将确实无效超出滑动窗口32kb的哈希键，并妥善应付地址addr的32kb以及64kb切换点。d大于1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，并更新该有效标示栏以标示所述储存格既有储存的内容无效；且该哈希运算硬件更以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。详细而言，d大于1时表示哈希行中所有储存格既有储存的哈希键的地址都超出了32kb滑动窗口的地址范围，该哈希运算硬件以{cur_addr[31:16],1’b0}(其中，1’b0表示1个二进制0，下同)更新该前缀地址prefix[31:15]，并以0更新该有效标示栏402中与所有既有储存格对应的比特，标示所述储存格既有储存的内容无效(即标示所述储存格无效)。其中所述储存格既有储存的内容表示所有有效标示栏402中值为1的比特对应的储存格中储存的内容，下同。此外，该哈希运算硬件就近地选择将输入哈希键储存到哈希行的储存格entry_0，并以1更新该有效标示栏402中与储存格entry_0对应的比特，标示储存格entry_0储存的内容有效,更以cur_addr[15:0]作为该输入哈希键的偏移量offset[15:0]存入储存格entry_0。值得注意的是，d大于1时，由于所有储存格既有储存的内容都是无效的，所以该哈希运算硬件可以选择将输入哈希键储存到储存格entry_0…entry_7中的任何一个或者就近地选择储存格entry_0。本发明在此并不作限制。d为1、prefix_old[15]为0、且cur_addr[15]为0时，该哈希运算硬件以{prefix_old[31:16],1’b1}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，且以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量cur_offset[15:0]存入该哈希表。详细而言，d为1、prefix_old[15]为0、且cur_addr[15]为0时表示输入哈希键与所有储存格既有哈希键的地址位于相邻且不同的64k段中，该哈希运算硬件以{prefix_old[31:16],1’b1}(其中，1’b1表示一个二进制1，下同)更新该前缀地址prefix[31:15]，以{1’b0,offset_old[14:0]}更新上述储存格既有储存的偏移量offset[15:0]。该哈希运算硬件根据有效标示栏402选择哈希行中一个无效的储存格(即选择有效标示栏402中值为0的比特对应的储存格)用以储存输入哈希键及其偏移量，且以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量offset[15:0]存入该选择的储存格。值得注意的是，该哈希行的所述储存格若都为有效(即有效标示栏402中所有的比特都为1)，该哈希运算硬件释出所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入；且所释出的储存格所载哈希键的地址与该输入哈希键的地址相距最远。具体而言，该哈希运算硬件使用输入哈希键的地址分别减去储存格中储存的既有哈希键地址，将得到8个数值，选择与这8个数值中的最大数值(即地址相距最远)对应的储存格将输入哈希键、以及该输入哈希键的偏移量存入。d为1、prefix_old[15]为1、且cur_addr[15]为0时，该哈希运算硬件以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量cur_offset[15:0]存入该哈希表。详细而言，d为1、prefix_old[15]为1、且cur_addr[15]为0时表示哈希行中所有有效的储存格中既有哈希键的地址与输入哈希键的地址位于同一个32k段，在这种情况下，哈希行的前缀地址和所有储存格中既有哈希键的地址都不需要更新(即保持现有值)。该哈希运算硬件根据有效标示栏402选择哈希行中一个无效的储存格(即选择有效标示栏402中值为0的比特对应的储存格)用以储存输入哈希键及其偏移量，该哈希运算硬件以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量cur_offset[15:0]。当该哈希行的所述储存格都为有效(即有效标示栏402中所有的比特都为1)时，该哈希运算硬件使用与d为1、prefix_old[15]为0、且cur_addr[15]为0时相同的处理流程释出所述储存格之一用于储存输入哈希键及其偏移量，此处就不再赘述了。d为1、prefix_old[15]为0、且cur_addr[15]为1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，更新该有效标示栏以标示该哈希行的所有储存格既有储存无效，并以cur_addr[15:0]作为该输入哈希键的偏移量cur_offset[15:0]存入该哈希表。详细而言，d为1、prefix_old[15]为0、且cur_addr[15]为1时表示哈希行中所有的既有储存格中储存的哈希键的地址都超出了32k滑动窗口的地址范围，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址prefix[31:15]，更以0更新该有效标示栏402中与所有有效储存格对应的比特，标示所述储存格既有储存的内容无效(即标示该哈希行的所有储存格均为无效)。此外，该哈希运算硬件选择将输入哈希键储存到哈希行的储存格entry_0，并以1更新该有效标示栏402中与储存格entry_0对应的比特，标示储存格entry_0储存的内容有效，并以cur_addr[15:0]作为该输入哈希键的偏移量cur_offset[15:0]存入该哈希表。值得注意的是，d为1、prefix_old[15]为0、且cur_addr[15]为1时，由于所有既有储存格中储存的内容都是无效的，所以该哈希运算硬件选择可以选择将输入哈希键储存到储存格entry_0…entry_7中的任何一个。d为1、prefix_old[15]为1、且cur_addr[15]为1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，并以cur_addr[15:0]作为该输入哈希键的偏移量cur_offset[15:0]存入该哈希表。详细而言，d为1、prefix_old[15]为1、且cur_addr[15]为1时表示输入哈希键与所有有效的储存格中存储的哈希键的地址位于相邻且不同的32k段中，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址prefix[31:15]，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量offset[15:0]。该哈希运算硬件根据有效标示栏402选择哈希行中一个无效的储存格(即选择有效标示栏402中值为0的比特对应的储存格)用以储存输入哈希键及其偏移量，并以cur_addr[15:0]作为该输入哈希键的偏移量offset[15:0]。当该哈希行的所述储存格都为有效(即有效标示栏402中所有的比特都为1)时，该哈希运算硬件使用与d为1、prefix_old[15]为0、且cur_addr[15]为0时相同的处理流程释出所述储存格之一将输入哈希键及其偏移量存入，此处就不再赘述了。d为0且prefix_old[15]为0时，该哈希运算硬件以cur_addr[15:0]作为该输入哈希键的偏移量cur_offset[15:0]存入该哈希表。详细而言，d为0且prefix_old[15]为0时表示哈希行中所有有效的储存格中储存的哈希键的地址与输入哈希键的地址位于同一个32k段，在这种情况下，哈希行的前缀地址和所有有效的储存格中储存哈希键的地址都不需要更新(即保持现有值)。该哈希运算硬件根据有效标示栏402选择哈希行中一个无效的储存格(即选择有效标示栏402中值为0的比特对应的储存格)用以储存输入哈希键，该哈希运算硬件以cur_addr[15:0]作为该输入哈希键的偏移量offset[15:0]。当该哈希行的所述储存格都为有效(即有效标示栏402中所有的比特都为1)时，该哈希运算硬件使用与d为1、prefix_old[15]为0、且cur_addr[15]为0时相同的处理流程释出所述储存格之一将输入哈希键及其偏移量存入，此处就不再赘述了。举例说明，输入哈希键填入储存格entry_3时，除了根据表格700的栏位cur_offset[15:0]将偏移量填入储存格entry_3，前缀地址栏404所载的前缀地址prefix[31:15]、以及有效的储存格entry_0～entry_2所载的三个偏移量offset[15:0]，甚至有效标示栏402也都需要适应性调整。调整方式可参考表格700的栏位prefix_new[31:15]以及offset_new[15:0]。图8示出哈希表的维护流程。对应一输入哈希键cur_key的储存需求，步骤s802根据该输入哈希键cur_key的一哈希值cur_value取得一哈希行cur_line。取得的该哈希行cur_line除了用作哈希键比较，更采以下动作进行更新。步骤s804计算一数值d(distance，距离)(d＝cur_addr[31:16]-prefix_old[31:16])，且判断两个比特prefix_old[15]以及cur_addr[15]。步骤s806填写该输入哈希键cur_key至该哈希行cur_line。一种实施方式中，选择有效标示栏402显示无效的储存格(闲置可填写)用以储存输入哈希键cur_key。一种实施方式中，有效标示栏402若显示所有储存格都有效，本案哈希运算硬件即释出与该输入哈希键cur_key的地址cur_addr具有最大地址差距的该个储存格用以储存输入哈希键cur_key。步骤s806更如表格700的prefix_new[31:15]、offset_new[15:0]以及cur_offset[15:0]栏位设定哈希行cur_line的前缀地址栏404以及各储存格(entry_0…entry_7)储存的偏移量，并相应调整有效标示栏402。步骤s808将该哈希行cur_line更新至该哈希表储存器204，使哈希表更新。前述技术也可用于其他尺寸的滑动窗口。在一实施方式中，哈希运算硬件在一个时钟周期内即可完成步骤s804、s806和s808中包含的所有操作。由于哈希键的地址位数为32位二进制数，所以当滑动窗口每滑过4g边界时，地址将从0开始重新计算，从而使得长度大于4gb(gigabyte)的原始数据串不能被正确压缩。为解决这一问题，当原始数据串的长度超过4gb时，可以在每次滑动窗口跨过4g边界时重置整个哈希表(即将哈希表中所有哈希行的有效标示栏402的所有比特置为0)。一种实施方式中，当滑动窗口大小为2m-1时，哈希行的储存格式所储存的前缀地址为prefix[(n-1):(m-1)]，且各储存格储存的偏移量为offset[(m-1):0]。n以及m为数值。m小于n。prefix[m-1]以及offset[m-1]为重叠比特。{prefix[(n-1):(m-1)],(m-1)’b0} offset[(m-1):0]对应原始数据串p的地址。相应滑动窗口的尺寸调整，哈希运算硬件调整其中设计，使addr[(n-1):0]＝{prefix[(n-1):(m-1)],(m-1)’b0} offset[(m-1):0]得以成立。数据压缩也可以软件方式实现。数据压缩软件也可采用前述哈希行储存格式。历史数据可以所述储存格式储存在系统存储器上。以该储存格式的哈希行而实现的数据压缩方法也属于本案欲保护范围。虽然本发明已以实施例揭露如上，然其并非用以限定本发明，任何熟悉此项技术者，在不脱离本发明的精神和范围内，当可做些许更动与润饰，因此本发明的保护范围当视后附的权利要求所界定者为准。[符号说明]100～异构计算平台；200～数据压缩器；202～哈希值运算方块；204～哈希表储存器；206～哈希键比较方块；208～滑动窗口储存器；210～最大长度辨识方块；212～匹配结果缓存器；214～排序逻辑；216～数据原文；218～编码器；220～压缩数据缓存器；222～接口；224～哈希表更新方块；226～哈希表管理方块；300～表格；400～哈希行的储存格式；402～有效标示栏；404～前缀地址栏；addr～地址；cur_addr～输入哈希键的地址；cur_offset～新填写储存格的偏移量；d～数值(＝cur_addr[31:16]-prefix_old[31:16])；entry_0…entry_7～储存格；key1、key2、key3、key4～哈希键；offset[15:0]～偏移量；offset_new、offset_old～既有储存的偏移量的新、旧版数值；p～原始数据串；prefix[31:15]～前缀地址；prefix_new、prefix_old～前缀地址的新、旧版数值；s802…s808～步骤。当前第1页1 2 3 当前第1页1 2 3
技术特征：1.一种数据压缩器，包括：
一哈希运算硬件，被配置为根据取自一原始数据串的一输入哈希键产生一哈希值，自一哈希表取得对应该哈希值的一哈希行，比对该哈希行的多个储存格，寻找对应该输入哈希键的至少一匹配哈希键；以及
一储存器，储存该哈希表，
其中：
该哈希行包括一前缀地址栏，储存一前缀地址；且
该哈希行的所述储存格各自载有一哈希键以及一偏移量；
其中，该哈希运算硬件根据该前缀地址及所述匹配哈希键的该偏移量得到所述匹配哈希键的地址。
2.根据权利要求1所述的数据压缩器，其中：
该哈希运算硬件根据该前缀地址及各偏移量得到所述储存格各自对应的哈希键的地址，并将所述对应的哈希键的地址与该输入哈希键的地址超过一滑动窗口范围的储存格设定为无效。
3.根据权利要求1所述的数据压缩器，其中：
该哈希运算硬件根据该前缀地址判断所述储存格既有储存的哈希键的地址是否都超过一滑动窗口范围，如果所述储存格既有储存的哈希键的地址都超过一滑动窗口范围，将所述储存格设定为无效。
4.根据权利要求1所述的数据压缩器，其中：
该哈希运算硬件选择该哈希行的所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入。
5.根据权利要求4所述的数据压缩器，其中：
该哈希行的所述储存格若都为有效，该哈希运算硬件释出所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入；且
所释出的储存格所载哈希键的地址与该输入哈希键的地址相距最远。
6.根据权利要求1所述的数据压缩器，其中：
该哈希行包括一有效标示栏，该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否。
7.根据权利要求1所述的数据压缩器，其中：
该前缀地址以及该偏移量间有一重叠比特。
8.根据权利要求7所述的数据压缩器，其中：
该前缀地址为prefix[(n-1):(m-1)]，n以及m为数值，m小于n；
上述偏移量为offset[(m-1):0]；且
prefix[m-1]以及offset[m-1]即上述重叠比特。
9.根据权利要求8所述的数据压缩器，其中：
该哈希运算硬件根据{prefix[(n-1):(m-1)],(m-1)’b0} offset[(m-1):0]得到所对应的哈希键的地址，其中，(m-1)’b0表示m-1个二进制0。
10.根据权利要求8所述的数据压缩器，其中，如果n为32，m为16，则：
该输入哈希键的地址为cur_addr[31:0]；
该前缀地址的一旧版数值为prefix_old[31:15]；
该哈希运算硬件将cur_addr[31:16]减去prefix_old[31:16]，获得的数值为d；
d大于1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，并更新该哈希行的一有效标示栏以标示所述储存格既有储存的内容无效，其中该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否；且
d大于1时，该哈希运算硬件更以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。
11.根据权利要求8所述的数据压缩器，其中，如果n为32，m为16，则：
该输入哈希键的地址为cur_addr[31:0]；
该前缀地址的一旧版数值为prefix_old[31:15]；
该哈希运算硬件将cur_addr[31:16]减去prefix_old[31:16]，获得的数值为d；
所述储存格既有储存的偏移量为offset_old[15:0]；
该哈希运算硬件更判读prefix_old[15]以及cur_addr[15]，其中：
d为1、prefix_old[15]为0、且cur_addr[15]为0时，该哈希运算硬件以{prefix_old[31:16],1’b1}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，且以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量存入该哈希表；
d为1、prefix_old[15]为1、且cur_addr[15]为0时，该哈希运算硬件以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量存入该哈希表；
d为1、prefix_old[15]为0、且cur_addr[15]为1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，更新该哈希行的一有效标示栏以标示所述储存格既有储存的内容无效，并以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表，其中该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否；
d为1、prefix_old[15]为1、且cur_addr[15]为1时，该哈希运算硬件以{cur_addr[31:16],1’b0}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，并以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表；且
d为0且prefix_old[15]为0时，该哈希运算硬件以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。
12.一种数据压缩方法，包括：
根据取自一原始数据串的一输入哈希键产生一哈希值；
自一哈希表取得对应该哈希值的一哈希行，其中，该哈希行包括一前缀地址栏，储存一前缀地址；
比对该哈希行的多个储存格，寻找对应该输入哈希键的至少一匹配哈希键，其中，该哈希行的所述储存格各自载有一哈希键以及一偏移量；及
根据该前缀地址及所述匹配哈希键的该偏移量得到所述匹配哈希键的地址。
13.根据权利要求12所述的数据压缩方法，还包括：
根据该前缀地址及各偏移量得到所述储存格各自对应的哈希键的地址；及
将所述对应的哈希键的地址与该输入哈希键的地址超过一滑动窗口范围的储存格设定为无效。
14.根据权利要求12所述的数据压缩方法，还包括：
根据该前缀地址判断所述储存格既有储存的哈希键的地址是否都超过一滑动窗口范围；及
如果所述储存格既有储存的哈希键的地址都超过一滑动窗口范围，将所述储存格设定为无效。
15.根据权利要求12所述的数据压缩方法，还包括：
选择该哈希行的所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入。
16.根据权利要求15所述的数据压缩方法，还包括：
该哈希行的所述储存格若都为有效，释出所述储存格之一将该输入哈希键、以及该输入哈希键的偏移量存入，其中，所释出的储存格对应的地址与该输入哈希键的地址相距最远。
17.根据权利要求12所述的数据压缩方法，其中：
该哈希行包括一有效标示栏，该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否。
18.根据权利要求12所述的数据压缩方法，其中：
该前缀地址以及该偏移量间有一重叠比特。
19.根据权利要求18所述的数据压缩方法，其中：
该前缀地址为prefix[(n-1):(m-1)]，n以及m为数值，m小于n；
上述偏移量为offset[(m-1):0]；且
prefix[m-1]以及offset[m-1]即上述重叠比特。
20.根据权利要求19所述的数据压缩方法，还包括：
根据{prefix[(n-1):(m-1)],(m-1)’b0} offset[(m-1):0]得到所对应的哈希键的地址，其中，(m-1)’b0表示m-1个二进制0。
21.根据权利要求19所述的数据压缩方法，其中，如果n为32，m为16，所述数据压缩方法还包括：
令该输入哈希键的地址为cur_addr[31:0]；
令该前缀地址的一旧版数值为prefix_old[31:15]；
将cur_addr[31:16]减去prefix_old[31:16]，获得为d的数值；
d大于1时，以{cur_addr[31:16],1’b0}更新该前缀地址，并更新该哈希行的一有效标示栏以标示所述储存格既有储存的内容无效，其中该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否；且
d大于1时，更以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。
22.根据权利要求19所述的数据压缩方法，其中，如果n为32，m为16，所述数据压缩方法还包括：
令该输入哈希键的地址为cur_addr[31:0]；
令该前缀地址的一旧版数值为prefix_old[31:15]；
将cur_addr[31:16]减去prefix_old[31:16]，获得为d的数值；
令所述储存格既有储存的偏移量为offset_old[15:0]；
更判读prefix_old[15]以及cur_addr[15]；
d为1、prefix_old[15]为0、且cur_addr[15]为0时，以{prefix_old[31:16],1’b1}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，且以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量存入该哈希表；
d为1、prefix_old[15]为1、且cur_addr[15]为0时，以{1’b1,cur_addr[14:0]}作为该输入哈希键的偏移量存入该哈希表；
d为1、prefix_old[15]为0、且cur_addr[15]为1时，以{cur_addr[31:16],1’b0}更新该前缀地址，更新该哈希行的一有效标示栏以标示所述储存格既有储存的内容无效，并以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表，其中该有效标示栏包括多个栏位以分别标示所述储存格各自有效与否；
d为1、prefix_old[15]为1、且cur_addr[15]为1时，以{cur_addr[31:16],1’b0}更新该前缀地址，以{1’b0,offset_old[14:0]}更新所述储存格既有储存的偏移量，并以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表；且
d为0且prefix_old[15]为0时，以cur_addr[15:0]作为该输入哈希键的偏移量存入该哈希表。
技术总结本发明公开一种数据压缩器及数据压缩方法，该数据压缩器包括：一哈希运算硬件，被配置为根据取自一原始数据串的一输入哈希键产生一哈希值，自一哈希表取得对应该哈希值的一哈希行，比对该哈希行的多个储存格，寻找对应该输入哈希键的至少一匹配哈希键；以及一储存器，储存该哈希表；该哈希行包括一前缀地址栏，储存一前缀地址。该哈希行的多个储存格各自载有一哈希键以及一偏移量，且该哈希运算硬件根据该前缀地址及所述匹配哈希键的该偏移量得到所述匹配哈希键的地址。
技术研发人员：李琳;惠志强
受保护的技术使用者：上海兆芯集成电路有限公司
技术研发日：2020.01.08
技术公布日：2020.06.09
