做纺织行业的网站,一个工程项目的整个流程,台州建设工程信息网站,成都校园兼职网站建设嵌入式Linux平台下随机序列算法设计嵌入式Linux平台下随机序列算法设计【摘 要】本文以多媒体播放器的随机不重复播放机能为切入点#xff0c;针对嵌入式平台实时性要求高#xff0c;处理速度不够快#xff0c;但系统存储歌曲量大的特点#xff0c;进行随机序列产生算法的设…嵌入式Linux平台下随机序列算法设计嵌入式Linux平台下随机序列算法设计【摘 要】本文以多媒体播放器的随机不重复播放机能为切入点针对嵌入式平台实时性要求高处理速度不够快但系统存储歌曲量大的特点进行随机序列产生算法的设计和实现并在ARM Linux平台下进行算法的设计检证。【关键词】嵌入式Linux随机序列播放 0 背景 随着近几年嵌入式系统总体能力的提升嵌入式多媒体应用越来越丰富。从低端的MP3播放器中端的workman到高端的智能手机音乐播放功能已经成为系统默认具备的功能。 嵌入式系统的存储能力已经跨入G时代。随身可携带的歌曲数量从几十首已经上升至几百首甚至上万首。 随机播放机能存在一种需求要将播放列表中的歌曲随机播放一遍在所有歌曲都播放一遍之前不能出现有重复播放的情况。 1 嵌入式系统的特点 嵌入式系统的能力现在虽然已经提升不少但和个人计算机相比较运算能力仍然无法匹敌个人计算机。并且还存在以下几种嵌入式系统特有的特点 *运算数据通常不能被交换到外部存储设备上程序可以使用的内存无法超过物理内存容量。 *人机交互需要快速的实时响应耗时过长的程序给用户较差的性能体验。 *外部存储器多为FLASH设备写入寿命有限制程序设计需要尽可能减少FLASH的写操作。 因此在嵌入式系统中随机播放的算法需要在时间以及空间的设计中获得一个平衡这样才能让用户有最好的体验。 2 算法的目标 *需要随机播放的总数是可变化。 *在总数给定的情况下随机产生的序列不能出现重复。 *时间和空间使用是平衡的满足嵌入式系统的特点。 3 解决方案 为了能够达成上述目标主要采用下面几种技术方案 *将随机序列的产生分配到每一次歌曲切换的时候而不是在初始化的过程中全部生成。 *将随机序列中某一个随机数的产生分解为按照16进制数位分别产生避免因为歌曲总量的提高导致时间出现指数级别的增长尽可能控制为线性增长。 *采用bitmap标示已经产生的随机数。 *采用用时申请的方式动态申请内存。 *记录随机序列产生的结果并提供回溯查询功能。 基于上面的技术方案在本设计中将整体算法划分为两个部分 *随机数列产生器用于产生不重复的随机数列。 *随机数列记录器用于记录已经随机数列并向外部提供访问接口。 4 数据结构设计 4.1 顶层数据结构 顶层数据结构(shuffle_t)包含随机数列产生器和随机数列记录器。 下面是数据结构定义 typedef struct _shuffle_t { /* 随机数列的最大值 */ int max /* 随机数列产生器 */ random_t *random /* 随机数列记录器 */ sequence_t *sequence }shuffle_t 在内存中的数据关系如图1所示。 图1 顶级数据结构示意图 4.2 随机数列产生器数据结构 随机数列产生器的数据结构(random_t)包含三个部分 *动态增长的bitmap池。 *优化的16以内的随机数产生器。 *按数位顺序产生代有检测功能的随机数列控制器。 下面是数据结构定义 /*双向循环链表 */ typedef struct _chain_t { /* 前一个链表 */ struct _chain_t *prev /* 后一个链表 */ struct _chain_t *next }chain_t /* digit池的描述头 */ typedef struct _pool_head_t { /* 双向循环链表 */ chain_t chain /* 当前digit池的总数 */ int total /* 当前digit池已使用个数 */ int used /* digit池首地址 */ char *data }pool_head_t /* digit池总入口 */ typedef struct _pool_t { /* bitmap池中一个bitmap单位的大小 */ int block_size /* bitmap池双向链表的表头 */ chain_t chain }pool_t /* 16以内随机数产生器 */ typedef struct _hex_random_t {
