转帖]调表算法分析
转帖]调表算法分析(1)
关于汽车里程表数据加密的思考
在汽车的仪表中一般用一种称之为EEPROM的器件来存储里程数据，EEPROM由于其器件的技术所限都存在一种通病：一般其数据的擦写次数在一百万次左右，有些旧型号的器件甚至只有十万次以下。而汽车的行驶过程中，如果以一公里记录一次的话，那么记录的里程就无法突破器件的擦写次数。为了解决这个问题，工程师必需使用一些办法来突破器件擦写次数的限制。因此在数据的存储或编码方式上就会出现与我们日常所见的数据方式不一样，此类车型包括：大众、奥迪、宝马、奔驰、本田等大部车型。
在使用半导体器件存储数据时，还会存在另一种问题：存储在器件中的数据不是绝对可靠的，由电路或外界带来的干扰，半导体器件本身的电子迁移等因素，都会造成存储器中的数据不可靠。工程师们为了解决这个问题，于是在数据的编码方面引入另一项技术：数据校验。也就是说，在记录数据的同时，为了能识别数据的正确与有校性，同时也记录了按一定的运算方法所得到的校验编码。此类车型包括：本田，福特，以及一部分的国产车。
对于目前的仪表来说，真正是由设计者特意将数据加密防止他人修改的车型很少见，目前所了解的也不过少数的几种车型，但对于以后的新车型会不会采用更严密的加密算法来加密数据，那就很难说。
由此看来，目前大多数仪表中里程数据的编码并不是我们平常所说的特意加密，而对于这些数据编码的算法我们是可以完全靠分析与学习来掌握的，在以后我会与大家一起来讨论、研究及分享这些算法，望大家多多支持！！！
今天我们来分析一种在汽车仪表中最常见的里程数据编码方式，这种编码方式的算法是为了解决存储器的读写次数而设计出来的。使用这种算法的车型包括：大部分的奥迪、大众、奔驰、宝马，以及小部分的国产车型，如奇瑞。并且其它的相当一部分车型的里程算法也是由这种算法演变或改进而来的。
在分析这种算法之前我先来谈一下关系到数据记录形式的两个问题：
一、反码与正码
在存储器中数据记录我们通常使用十六进制的正码记录方法，如把12345（十进制）记录为：3039（十六进制）。
但在汽车仪表中我们还会看到另一种记录方式：十六进制反码，如把12345（十进制）记录为：CFC6（十六进制反码）。
那么反码与正码怎么转换呢？我们看一下用十六进制的计算：CFC6=FFFF-3039;
其实我们还可以用另一种更直接简单的转换方式，只要按下表对照进行一位对一位的转换即可：
正码：0 1 2 3 4 5 6 7 8 9 A B C D E F
反码：F E D C B A 9 8 7 6 5 4 3 2 1 0
二、数据高低位问题
由于CPU设计和存储器设计的差异，对于同一个16位的十六进制数记录时可能有高位在前或低位在前的设计差异。
如数据3039（十六进制），在某些仪表中会记录为：3930。
在调表之前我们必需弄清，我们的仪表是用那一种数据记录方式，其中有四种可能，即：正码+高位在前，正码+低位在前，反码+高位在前，反码+低位在前。
说到这里我们开始进入我们的正题，今天我们所要讲的里程算法。
如果我们在仪表的存储数据中看到这样的数据：3039 3039 3039 3039 3039 3039 3038 3038；
一组数值很相近，连在一起（有可能是8组，也有的是16组），这就是我们所要的里程数据。
现在我们假设数据的高低位及正反码的问题已解决，已经把数据统一转为正码、高位在前，并且只讨论八组数据的情况，我们看几个例子：
1KM : 0001 0000 0000 0000 0000 0000 0000 0000
2KM : 0001 0001 0000 0000 0000 0000 0000 0000
3KM : 0001 0001 0001 0000 0000 0000 0000 0000
8KM : 0001 0001 0001 0001 0001 0001 0001 0001
9KM : 0002 0001 0001 0001 0001 0001 0001 0001
10KM : 0002 0002 0001 0001 0001 0001 0001 0001
大家很快就看出来，里程数就是把全部的数据都加起来的结果，但在大部分的车型中是每跑两公里记录一次数据的，这时候我们得出的数据应该都乘以2才是实际的里程数，如上数据那就分别是：2KM,4KM,6KM,16KM,18KM,20KM。
在上次我们已经分析了大众车系的调表算法，今天我们来分析一下丰田车系的调表算法
丰田车系的里程算法与大众的里程算法都同样是为了解决芯片擦写次数限制问题而产生的。
在分析丰田算法前我们先介绍两个名词：
字节:在十六进制的数据中我们把两个连着的字符称为“字节”，如：FF、00、12、34等
字 ：由连着的两个字节组成的数据称之为“双字节”或“字”，如：80FF、1032、7ABE等。
在绝大部分的调表算法中都使用“字”作最小的计数单位。
现在我们来看一组丰田车的里程数据：
97486公里记录为：80FF FFFF FFFF FFFF 7A8B F6FF 7A8B F6FF 7A8B F6FF
这组数据为丰田车的里程记录数据，数据分为两部分。前一部分由四个字组成。即我们看到的：80FF FFFF FFFF FFFF，这组数据记录了从
0到4的里程数。
如：0KM FFFF FFFF FFFF FFFF
如：1KM 80FF FFFF FFFF FFFF
如：2KM 80FF 80FF FFFF FFFF
如：3KM 80FF 80FF 80FF FFFF
如：4KM 80FF 80FF 80FF 80FF
即是有几个80FF就为几公里。
那么超过了4公里是怎么记录的呢？
那就是后半部的数据了。在后半部的数据中我们看到了重复了三次的“7A8B F6FF”，这三组数据代表的数值都是一样的，只是为了提高数据的可靠性而重复记录了三次，在修改数据时我们必须把三组数据同时修改，且其数值都必须一样。
现在我们来分析一下这组数据的含义。首先我们先看一下下面的这个数据转换表：
6 7 8 9 A B C D E F
| | | | | | | | | |
9 8 7 6 5 4 3 2 1 0
对照上表我们可以把数据：7A8B F6FF 转换为： 8574 0900。
在8574 0900这组数据中它们的排列方式为：[十位][个位][千位][百位] [十万位][万位][千万位][百万位]。
我们将它们按我们日常的记数顺序重新排列一下，可得到：00097485。
97485加上前面一个80FF代表的一公里，那么可得到公里数为97486公里。
为了让大家加深印象，我再举例几个里程数据：
80FF FFFF FFFF FFFF EF78 FFFF EF78 FFFF EF78 FFFF ：8710+1=8711km
80FF 80FF FFFF FFFF EFFF FFFF FFFF FFFF FFFF FFFF ：10+2=12km
FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF ：0+0=0km
80FF FFFF FFFF FFFF 669A E8FF 669A E8FF 669A E8FF ：176599+1=176600km
80FF 80FF 80FF FFFF FFCF 69FF FFCF 69FF FFCF 69FF ：963000+3=963003km
80FF 80FF 80FF 80FF CAFF FFFF CAFF FFFF CAFF FFFF ：35+4=39km
注：
[1]在某些丰田车中以FF80代替80FF；
[2]在某些车中每个80FF代表2公里；
[3]在调表时建议大家可以把前半部数据都改为FFFF，只需修改后半部三组数据，可以简化计算。
此算法适用车型：97-2000年款丰田佳美、98款-2000年凌志LS400、96-2000款凌志ES300、97-2000年款GS300，以及部分其它车型。
