如何确定用户在汇编语言 X86 中输入的字符串中单词的频率?

2023-12-09

我是汇编语言编程的完全初学者。我需要帮助编写一个汇编语言程序来从用户那里获取字符串,计算并显示每个单词在用户输入的字符串中出现的次数。

例如,如果用户输入:

Hello Hello what is new Hello what is not new

输出应该是:

Hello   3
what    2
is      2
not     1
new     2

下面的代码将给出字符串中字符的频率。但是,我不知道如何编辑以便我可以跟踪单词而不仅仅是字符,然后能够显示这些单词及其相应的频率。

INCLUDE Irvine32.inc

Get_frequencies PROTO,
    pString:PTR BYTE,   ; points to string
    pTable:PTR DWORD    ; points to frequency table

.data
freqTable DWORD 256 DUP(0)
;aString BYTE 1,2,"This is extremely difficult for the experienced",0

aString BYTE 80 DUP(0),0

str1 BYTE "*** Constructing a Frequency Table *** (DEMO)",
    0dh,0ah,0dh,0ah,
    "Enter between 1 and 80 characters: ",0

.code
main PROC

    call Clrscr
    mov  edx,OFFSET str1
    call WriteString

    mov  ecx,SIZEOF aString - 1
    mov  edx,OFFSET aString
    call ReadString

    INVOKE Get_frequencies, ADDR aString, ADDR freqTable
    call DisplayTable

   exit
   main ENDP

;-------------------------------------------------------------

  Get_frequencies PROC,
    pString:PTR BYTE,   ; points to string
    pTable:PTR DWORD    ; points to frequencey table

;
; Constructs a character frequency table. Each array position
; is indexed by its corresponding ASCII code.
;
; Returns: Each entry in the table contains a count of how
; many times that character occurred in the string.
;-------------------------------------------------------------

mov esi,pString
mov edi,pTable
cld     ; clear Direction flag (forward)

L1: mov eax,0       ; clear upper bits of EAX
   lodsb        ; AL = [ESI], inc ESI
   cmp al,0     ; end of string?
   je  Exit_proc        ; yes: exit
   shl eax,2        ; multiply by 4
   inc DWORD PTR [edi + eax]    ; inc table[AL]
   jmp L1       ; repeat loop

 Exit_proc:
    ret
 Get_frequencies ENDP

  ;-------------------------------------------------------------

 DisplayTable PROC

  ;
  ; Display the non-empty entries of the frequency table.
  ; This procedure was not required, but it makes it easier
  ; to demonstrate that Get_frequencies works.
  ;-------------------------------------------------------------

  .data
  colonStr BYTE ": ",0
  .code
  call Crlf
  mov ecx,LENGTHOF freqTable    ; entries to show
  mov esi,OFFSET freqTable
  mov ebx,0 ; index counter

 L1:    mov eax,[esi]   ; get frequency count
        cmp eax,0   ; count = 0?
        jna L2  ; if so, skip to next entry

         mov eax,ebx    ; display the index
         call WriteChar
         mov edx,OFFSET colonStr    ; display ": "
         call WriteString
         mov eax,[esi]  ; show frequency count
         call WriteDec
         call Crlf

  L2:   add esi,TYPE freqTable  ; point to next table entry
        inc ebx ; increment index
        loop L1

        call Crlf
        ret
      DisplayTable ENDP

      END main

这是我迄今为止尝试实施彼得的回答中建议的强力搜索的结果:

 .data
 str2 BYTE "one two three",0

 .code
  main proc
   mov  edi,OFFSET str2
    Mov esi,edi
    Mov Ecx, 0  ;reset ecx to 0
    Not Ecx     ;set Ecx to -1 or highest possible integer
    Mov Al, ' ' ;Initialize a1 to delimiter of (space) ' '
    Cld         ;Clear Direction Pointer
    Repne Scasb ;scan edi one byte at a time until delimiter found
    Not Ecx
    Lea Eax, [ecx-1] ;Set Eax to index of found delimiter
    Xchg Esi, Edi  ;Take Edi which is now equal to string after found       delimiter and put in esi

    mov edx, esi
    call WriteString    

 main endp
 end main

这会打印“二三”,但我希望它打印“一”。


与使用 C 或任何其他已知语言相比,asm 并没有什么特别之处,会让您选择不同的算法。

这是任务吗?它似乎比您通常想要在 asm 中执行的操作更复杂。然而,如果它只适用于短字符串,那么一个非常糟糕的暴力算法,除了字符缓冲区之外不使用任何数据结构,会更容易实现(见下文)。

可打印的 ASCII 字符少于 128 个,因此计数表既小又简单。

字符和单词的区别在于可能的单词数量是无限的(除非内存大小限制),所以您不能直接使用单词作为计数表的索引。即使使用 4 字符字作为计数表的 4 字节索引也会使计数表大小 = 2^32 条目。


将计数表算法从字符调整为单词的最直接方法是使用某种字典数据结构, 像一个哈希表, tree,甚至是一个基数树/特里树。每个条目将一个单词映射到其计数器。

The simplestword:count 可能的“字典”将是一个未排序的数组
struct {char *word; int count;} histogram[];你线性搜索。这效率不高,但在 asm 中很容易实现。可以通过存储显式长度的字符串来加速单词比较,例如int wordlen; char *wordstart这样你就可以直接指向你的字符串而不必存储0终结者。然后你可以在查看字节之前检查单词的长度是否相同,并且memcmp可以比strcmp.

这很糟糕,因为它是对每个输入单词的计数数组的线性搜索,但它仍然可能比下面的暴力方式更好,即扫描(并复制)每个输入单词的字符串的整个其余部分。保持这个数组排序(插入排序风格)可能会更好,也可能不会更好,在找到单词时允许使用二分搜索进行 O(log(n)) 访问。可能有一些巧妙的权衡,例如间隙数组(通过一种方式来指示未使用的插槽),可以让特定位置的插入只需要复制有限的数量。或者当然还有经典的字典数据结构,例如哈希表或树。

另一种选择是对单词列表进行排序,然后循环遍历排序后的列表,计算重复项。或者在排序时累积重复计数,即当您的输入单词列表太大而无法一次全部装入内存时,这是一个有趣的问题.


您当前的 char 循环可能会更好:

这就是我可能会做的:

;; tighter version of your char-count loop
   xor   eax, eax                    ; clear upper bits of EAX
L1:
   lodsb                          ; AL = [ESI], inc ESI
   inc   DWORD PTR [edi + eax*4]  ; inc table[AL]
   test  al,al                    ; Set flags based on AL
   jz    L1                       ; loop if it's not the end of the string
   ;; fall through when done
   ;;dec   DWORD PTR [edi]          ; undo the count of the zero if you care

或者更有可能的是movzx eax, byte [esi] / inc esi,这比lodsb,避免合并到旧 EAX 中的成本。

这确实会计算终止 0,但会保存循环中的指令。通过在循环之外添加更多代码,您可以避免这种情况,同时仍然保持循环较小。

因为我们左移作为寻址模式的一部分,我们不需要在循环内将 eax 归零。使用xor-归零还可以避免在仅写入 al 后读取 eax 时导致部分寄存器变慢,如果您关心性能。


一种可能更容易在 asm 中实现的暴力算法

这对于长字符串来说效果会很糟糕,但对于非常短的字符串来说可能会非常好。主要优点是易于实现,但对于非常短的字符串(例如 128 字节),它在性能方面可能与树或散列具有竞争力。

  • 找到第一个单词的结尾
  • 搜索rest字符串中该单词出现的次数。 (记住只匹配完整的单词,而不是像strstr(3))
  • 在每次匹配时,将字符串的其余部分复制到左侧,从字符串中删除该单词。 (也删除第一个词。)
  • 重复直到字符串为空

(您不必复制第一个匹配项,只需前进指针,以便下一个搜索从它的末尾开始。如果没有找到重复项,则无需进行任何复制。)

这会花费大量时间来复制字符,但我们需要避免重复(当我们稍后处理某个单词的最后 n-1 次出现时,再进行一次计数)。通过搜索已计算单词的另一个数据结构进行重复检查可以让您避免复制,但如果您打算这样做,您也可以将字符串和直方图一次传递到找到的单词“字典”中,请参阅多于。

但这本身会花费额外的周期和代码,并且所有未来的搜索都将搜索这些已经计算过的单词。如果您要使用一系列已经找到的单词,您也可以

您可以使用以下命令进行复制rep movsb,我认为这仍然适用于重叠的 dst 和 src。 (但如果它们紧密重叠,则速度不快)。

另一种选择是拥有第二个相同大小的缓冲区,因此您只需要复制整个字符串,同时删除您正在计算的当前单词的所有出现次数:

从字符串 A 中的第二个单词开始:

  • 将字符复制到字符串 B 中。
  • when you reach the end of a word, check if it's a match for the current word you're looking for.
    • if yes: count++ and dst-=length_of_current_countword。当您检测到要查找的单词时,您将倒回目标指针(edi) 到开头,因此将来的复制将覆盖它。 IE。此时您基本上可以免费取消复制它。
  • 重复直到到达字符串 A 的末尾
  • 打印当前单词和计数。
  • 如果字符串 B 不为空,它将成为新字符串 A 等。也许将指向 A 和 B 的指针保留在寄存器或内存中,以便可以交换它们,而不是直接使用静态存储的地址。或者只是用愚蠢的方式将 B 复制到 A 而不进行任何更改。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何确定用户在汇编语言 X86 中输入的字符串中单词的频率? 的相关文章

  • intfmt: db "%d", 10, 0 在汇编中的含义

    我最近在我的一个汇编文件的顶部看到了这个 并意识到我在打印整数的过程中花了很长时间使用它 而没有真正意识到它最初来自哪里 在我的基本汇编模板中使用 或 10 0 是什么结尾的意思是 section data intfmt db d 10 0
  • 如何反汇编、修改然后重新组装 Linux 可执行文件?

    无论如何 这可以做到吗 我使用过 objdump 但它不会产生我所知道的任何汇编器都可以接受的汇编输出 我希望能够更改可执行文件中的指令 然后对其进行测试 我认为没有任何可靠的方法可以做到这一点 机器代码格式非常复杂 比汇编文件还要复杂 实
  • Windows 上 PE 文件 (exe) 的最小文件大小是多少?以及最小内存分配? [复制]

    这个问题在这里已经有答案了 Windows 上 PE 文件 exe 的最小文件大小是多少 以及最小内存分配 我 使用 VS 10 附带的 MASM ml exe 和 link exe 组装了以下代码 我不能忽略 kernel32 lib 和
  • Python 删除额外的特殊 unicode 字符

    我正在 python 中处理一些文本 它内部已经采用 unicode 格式 但我想删除一些特殊字符并用更标准的版本替换它们 我目前有一条看起来像这样的线路 但它变得越来越复杂 我发现它最终会带来更多麻烦 tmp infile lower r
  • 将十进制转换为十六进制

    首先 这是家庭作业 我正在尝试将 5 位数字读入寄存器 bx 假定该数字不大于 65535 16 位 以下是我尝试这样做的方法 但是 当我尝试打印该号码时 我仅打印输入的最后一位数字 这让我猜测 当我向 bx 添加另一个数字时 它会覆盖以前
  • movsbl指令的作用是什么? [复制]

    这个问题在这里已经有答案了 我在网上搜索过 但找不到明确的示例来理解该指令的作用 因此 如果有人可以举一个例子 这对我来说将会非常有帮助 用符号从字节扩展到长字移动 在Intel语法中 该指令的助记符是MOVSX 当变量类型为 C 时 C
  • 如何在 AVX/AVX2 中递增向量

    我想使用内在函数来增加 SIMD 向量的元素 最简单的方法似乎是为每个元素加 1 如下所示 note vec inc之前已设置为1 vec mm256 add epi16 vec vec inc 但是是否有任何特殊指令来增加向量 类似于in
  • 在现代 x86-64 上计算 64 位整数的整数 Log10 的最快方法是什么?

    标题 我找到了大量 32 位示例 但没有找到完整的 64 位示例 使用这个帖子 https codegolf stackexchange com questions 47290 fastest way to compute order of
  • x86:寄存器操作为内存内容和内存地址?

    寄存器 gt 内存地址 gt 内存内容 内存地址 gt 内存内容 上面的模型正确吗 而且 如果是的话 你能建议我是否认为正确吗 movl eax ebx gt 它将 eax 的内存地址移动到 ebx 这也会导致内容移动 movl eax e
  • Linux Shellcode“你好,世界!”

    我有以下可用的 NASM 代码 global start section text start mov eax 0x4 mov ebx 0x1 mov ecx message mov edx 0xF int 0x80 mov eax 0x1
  • 为什么 VC++ 编译器 MOV+PUSH args 而不是仅仅 PUSH 它们? x86

    在 VC 的反汇编中 正在进行函数调用 编译器在压入本地指针之前将其 MOV 到寄存器 memcpy nodeNewLocation pNode sizeCurrentNode 0041A5DA 8B 45 F8 mov eax dword
  • ARM 汇编:从 STDIN 获取字符串

    我目前正在学习 CS 课程 我们刚刚开始在 Raspberry Pi 上使用 ARM Assembly 事实证明这相当困难 想知道是否有人可以提供帮助 我当前的任务是从 stdin 获取一个字符串 使用 scanf 并计算其中的字符数 然后
  • 英特尔 JCC 勘误表 - 用于缓解的前缀有什么影响?

    Intel 推荐 https www intel com content dam support us en documents processors mitigations jump conditional code erratum pd
  • X86 从 stdin 读取并写入 stdout,无需引用标准库

    我是 X86 汇编语言的初学者 我知道如何使用内置函数从标准输入读取数据并写入标准输出 但我不确定如何使用简单的汇编代码 即操作寄存器和利用系统调用 来做到这一点 include
  • 电路解码所需的最小输入位数

    我正在学习计算机体系结构 并且正在阅读有关编码器和解码器的内容 在 MIPS 处理器中 操作码有 6 位 我想知道构建解码器来解码操作码需要多少输入位 我知道解码器是一个组合电路 它将二进制信息从 n 个输入线转换为最多 2 n 个唯一的输
  • 将 2 个数字与汇编进行比较[关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 我有以下代码 我想完成汇编代码 如下
  • 如何使用 LOCK ASM 前缀来读取值?

    我知道如何使用 LOCK 来线程安全地递增一个值 lock inc J 但是如何以线程安全的方式读取 J 或任何值 LOCK 前缀不能与 mov 一起使用 如果我执行以下操作 xor eax eax lock add eax J mov J
  • 如何在 Linux 中制作一个将文件转换为大写的 x86 汇编程序?

    我找到了一个名为 ProgrammingGroundUp 1 0 booksize pdf 的 pdf 文件 其中一个项目是制作一个汇编程序 该程序接收文件并将其转换为大写 section data CONSTANTS system cal
  • 编写一个新的 jit

    我有兴趣用 C 启动我自己的 JIT 项目 我对汇编或编译器设计等并不熟悉 但是 我对生成的机器代码格式非常不熟悉 比如 当一切都说了和完成后 mov 指令实际上是什么样子 是时候调用它了函数指针 那么 创建这样的东西的最佳资源是什么 编辑
  • 如何找出英特尔处理器上的指令触及了哪条高速缓存线?

    我读了这篇文章关于 Meltdown Spectre 漏洞利用 http www theregister co uk 2018 01 04 intel amd arm cpu vulnerability 允许利用 CPU 中的硬件错误从内核

随机推荐

  • UTF8 和日语字符

    问题 外来字符未按应有的方式显示 这包括德语 日语 俄语和除英语之外的所有其他语言 完美运行 PHP 通过 jQuery AJAX 调用调用 MySQL 它应该返回信息并将其显示在页面上 数据被调用并显示 然而 对于非英语字符 结果显示为
  • 如何根据 iFrame 内容的大小“增长”iFrame?

    我正在动态加载 iFrame 有些页面比其他页面 更高 我希望 iFrame 能够相应地增长 是否可以 如果是这样 怎么办 是的 jquery 是可以的 父页面代码 iframe页面上的脚本 function alertSize var m
  • 如何实现网页的实时更新?

    Google 的 GMail 服务之所以能做到这一点 是因为它集成了 Google Talk 而 Etherpad 现在的 typewith me 使 Google Wave 等使用的系统闻名 当其他用户对页面进行更改时 所有此类系统都会立
  • 禁用 LLVM 10 C++ API 的常量折叠

    我正在使用 LLVM C API 为 C 语言的子集编写编译器前端 我注意到生成的 IR 总是应用恒定的折叠优化 但我想禁用此功能并获得忠实的 未优化的 IR 有什么办法可以做到这一点吗 以下是我用来从模块生成 IR 的代码 llvm ve
  • 当通过 javascript/jquery 更改值时,多个选择不会更新

    我有一个多重选择 其中每个选项都设置了一个类 根据类别 我可以预先选择特定类别的所有选项 因此用户不必自己选择所有选项 到目前为止 它运行良好 直到我通过单击手动选择一个选项 从现在开始 预选似乎不再起作用了 但只有视觉效果不再起作用 选项
  • 使用 Youtube Iframe API 创建的视频播放器停止与 Chrome v.85 配合使用

    我在将 Youtube iframe API 与最新稳定版本的 Chrome 版本 85 一起使用时遇到问题 我知道一个月前一切都可以正常工作 但现在 即使完全遵循 Youtube iframe API 文档中找到的最基本的示例 https
  • INotifyCollectionChanged 未更新 UI

    我有一堂课 如下所示 为了简洁起见 我删除了所有功能 public class PersonCollection IList
  • 如何在部署到 Vercel 的 Next.js 应用程序中正确设置环境变量?

    我正在 Next js 中构建我的网络应用程序 并且我一直在做一些测试 我正在做的是将我的代码推送到 GitHub 然后从那里将项目部署到 Vercel 我正在使用 Google API 依赖项 它需要一些客户端 ID 和客户端密钥 以便我
  • 查找组中最常见的观察结果[重复]

    这个问题在这里已经有答案了 数据框 B pd DataFrame b II II II II II I I I MOST FREQUENT 1 2 2 1 1 1 2 2 我需要获取列中出现次数最多的值MOST FREQUENT对于每组 p
  • #[inline] 可以在特征方法声明和实现中使用吗?

    我有一些小方法的特征 这些方法通常作为实现结构所具有的其他方法的单行包装器来实现 如果我想确保特征方法是内联的 我应该放置 inline always 在特征定义内 或在impl对于每个结构 我更愿意简单地将其放入特征定义中 但据我所知 这
  • 如何将最新更改拉取到 GitHub 中我当前的工作分支?

    假设我在分支 abc test git pull origin master 这是否会将 master 分支与我当前的分支 abc test 合并 或者我是否需要运行更多命令 tl dr run git fetch获取最新更改 然后运行gi
  • 在 2.0.5 中,将 cassandra 作为服务启动不起作用,sudo cassandra -f 有效

    当我尝试在 ubuntu 12 04 上启动 cassandra 时 通过 Datastax 安装 dsc20包 作为服务如下 sudo 服务 cassandra 启动 it says 无法访问 Cassandra 的 pidfile 日志
  • 如何使用弹出窗口在 JavaScript 中构建一个简单的图片库

    我在互联网上寻找帮助 但我无法让它工作 有人能给我一个如何编写这样的代码的例子吗 我会调整图像的大小 并为弹出窗口提供一个缩略图大小的图像和一个更大的图像 我希望用户单击缩略图大小的图像并在弹出窗口中显示全尺寸的图像 我是 Javascri
  • Excel:如何使用VBA检查单元格是否为空? [复制]

    这个问题在这里已经有答案了 通过VBA 我如何检查一个单元格是否是另一个具有特定信息的空单元格 例如 如果 A A 产品特殊 且 B B 为 null 那么 C1 产品特殊 另外 我如何使用For Each循环在Range以及如何返回另一个
  • 选择不同数据库中的列

    是否可以在位于同一服务器上的不同数据库之间执行选择 或插入 语句 如果是 怎么办 您可以使用以下语法指定数据库databasename tablename Example SELECT mydatabase1 tblUsers UserID
  • 如何彻底卸载oracle 11g?

    如何从笔记本电脑上卸载 Oracle 11g 软件附带的卸载程序并不能完全卸载所有组件 我用Oracle12c试了一下 留下了很多程序 我尝试手动删除这些文件 但 BIN 目录中的某些 dll 文件无法访问 我想用 11g 做正确的事 有什
  • 使用jquery从父页面访问子IFrame中的元素

    我尝试使用以下代码从父文档访问 iframe 中文档的元素 但由于某种原因无法使其工作 父级 html
  • 需要帮助使用 GIOService(GLib、Glib-GIO)实现简单的套接字服务器

    我正在学习使用 GLib 编写简单 高效的套接字服务器的基础知识 我正在尝试 GSocketService 到目前为止 我似乎只能接受连接 但随后它们立即关闭 从文档中我无法弄清楚我错过了哪一步 我希望有人能为我阐明这一点 运行以下命令时
  • 如何提高最低成本路径模型的模拟速度

    通过使用网络扩展 以下代码在两个多边形 由多个面片组成 之间构建成本最低的路径 to calculate LCP ID polygon 1 ID polygon 2 let path let path cost 1 Define polyg
  • 如何确定用户在汇编语言 X86 中输入的字符串中单词的频率?

    我是汇编语言编程的完全初学者 我需要帮助编写一个汇编语言程序来从用户那里获取字符串 计算并显示每个单词在用户输入的字符串中出现的次数 例如 如果用户输入 Hello Hello what is new Hello what is not n