蓝桥杯13届第二场eEPROM

题目描述

电子产品中，通常用 EEPROM 存储程序和数据，而 EEPROM 的容量和读写速度相比 RAM 要小和慢得多，因此 EEPROM 被广泛应用于存储程序配置信息、数据备份等不需要高速读写的场合。为了提高 EEPROM 的读写速度，可以使用更高级别的技术，例如缓存、压缩、DMA 等。

现在，您需要完成一组 EEPROM 相关的操作模拟，包括写入操作、读取操作、写入缓存操作、从缓存读取操作，具体如下：

- 写入操作：从固定地址 addr 开始，连续写入 len 个字节的数据 data，其中 len <= 1024，每个字节的值为 0-255，如写入 {1,2,3,4,5} 到地址 10，即为0x0A，则地址 10-p 的值为 1，地址 p+1 的值为 2，直到地址 p+len-1 的值为 5。
- 读取操作：从固定地址 addr 开始，连续读取 len 个字节的数据 data，其中 len <= 1024，将读取到的数据存储到数组 data 中，如从地址 10-p 中读取长度为 5 的数据，则读取到的数据为 {1,2,3,4,5}。
- 写入缓存操作：从固定地址 addr 开始，连续将 len 个字节的数据 data 写入到内部缓存，其中 len <= 1024，每个字节的值为 0-255，如写入 {1,2,3,4,5} 到地址 10，即为0x0A，则缓存内 0-p 的值为 1，缓存内 p+1 的值为 2，直到缓存内 p+len-1 的值为 5。
- 从缓存读取操作：从固定地址 addr 开始，连续从内部缓存中读取 len 个字节的数据 data，其中 len <= 1024，将读取到的数据存储到数组 data 中，如从地址 10-p 中读取长度为 5 的数据，则缓存内的数据还是不变的，读取到的数据为 {1,2,3,4,5}。

题目分析

这道题目的本意是通过位运算来实现读写操作，需要熟练掌握位运算技巧，个人感觉难度偏高。但是可以选择暴力做法：用数组模拟写入、读取、缓存操作，但是这样显然没有熟练掌握位运算技巧更加有利。

代码实现

暴力做法

这里就不给出实现，感觉也比较简单，有兴趣的可以自己思考。

位运算做法

在本篇文章中，我们将采用位运算来实现读写缓存操作，下面分别说明。

时间和空间复杂度

算法时间复杂度：O(len)
算法空间复杂度：O(1)

思路

在编程中，操作硬件的数据往往以位为单位，这是由硬件的特殊性决定的。本题中如果仅仅使用常规数组来完成读写操作，在比较位运算技巧的同学面前会显得不那么高端，因此在下面我们将采用位运算的方式来进行相应的操作。

读数据

假设我们要从地址 addr 开始读 len 个字节，按位运算的做法如下：

for(int i=0;i<len;i++)
{
byte[i] = ~pgm_read_byte_near(addr+i) & 0xff;
}

其中 pgm_read_byte_near 是一个库函数，可以实现从 flash memory 中读取一个字节数据。由于 EEPROM 属于 flash memory，所以该函数可以读取 EEPROM 中的数据。

总体来说，这个语句执行起来比较耗时，但是在数据量不大的情况下，应该不会引起问题。我们的目标是在数量很大的情况下，也能够使用位运算的方式快速地读取数据，下面介绍具体的实现方法。

注意到我们已经处理的字节只有 byte[0]~byte[j-1]，那么在处理完 byte[j] 后，我们将完成的部位保存到 byte[j] 中。不妨假设从字节的第 k 位开始，第 k~k+7 位等于我们要读的 len-j 个字节的内容，那么完全可以通过移位 (>>k)，加法、位运算 (|) 来快速实现读取操作，具体代码如下：

uint8_t temp = 0;
for(int i=0;i<len;i++)
{
if(i%8 == 0) //记录的字节已处理完毕，需要读取新的字节
{
temp = ~pgm_read_byte_near(addr+(j++)) & 0xff;
}
byte[i] = (temp>>(i%8)) & 1;
}

写数据

假设我们要从地址 addr 开始写 len 个字节，按位运算的做法如下：

for(int i=0;i<len;i++)
{
uint8_t a = ~byte[i] & 1;
uint16_t p = addr+i;
uint8_t r = pgm_read_byte_near(p) & (~(1<<a));
uint8_t w = r | (byte[i]<<a);
pmg_write_byte_near(p,w);
}

其中，pmg_write_byte_near 是一个库函数，可以实现向 flash memory 中写入一个字节数据。由于 EEPROM 属于 flash memory，所以该函数可以写入 EEPROM 中的数据。

同样地，这个语句执行起来也比较耗时，因此在下面我们将采用位运算的方式来进行相应的操作。

写入缓存

假设我们要从地址 addr 开始写 len 个字节到缓存中，那么按位运算的做法如下：

for(int i=0;i<len;i++)
{
uint8_t a = ~byte[i] & 1;
uint16_t p = addr+i;
cache[p] |= (byte[i]<<a);
}

cache 是一个数组，用来存储缓存数据。

从缓存读取

假设我们要从地址 addr 开始读取 len 个字节，按位运算的做法如下：

uint8_t temp;
for(int i=0;i<len;i++)
{
uint8_t a = ~byte[i] & 1;
uint16_t p = addr+i;
temp = (cache[p]>>a) & 1;
byte[i] = ~temp & 1;
}

cache 是一个数组，用来存储缓存数据。

测试与运行效果

模拟器

模拟器输出截图如下：

本地测试

用C++代码实现，本地环境由 Debian Linux 系统，GNU GCC 编译器，125MHz的 ATmega128Lc 单片机（仿真环境）组成。本题测试结果均通过。