0

我正在努力完成以下任务：编写一个带有两个参数的 C 程序：input.bin 和 output.bin。

  • input.bin 和 output.bin 是二进制文件
  • input.bin 最多可以包含 65535 个 uint16_t 数字
  • 文件 output.bin 必须由程序创建，并且必须包含 input.bin 中按升序排序的数字
  • 您的程序只能使用 256 KB RAM 和 2MB 磁盘空间

所以，我想我可以尝试用计数排序来做到这一点。这就是我所做的：

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <stdint.h>
#include <unistd.h>

int main(int argc, char* argv[]) {
    if(argc != 3)
        errx(1, "Usage: %s <input.bin> <output.bin>", argv[0]);

    const char * in = argv[1];
    char * out = argv[2];

    struct stat st;
    if(stat(in, &st) == -1)
        err(2, "fail to stat file %s", in);

    if(st.st_size % sizeof(uint16_t) != 0)
        errx(3, "file %s is corrupted", in);

    if(st.st_size / sizeof(uint16_t) > 0xffff)
        warnx("overflow in file %s may occur", in);

    int fd_i = open(in, O_RDONLY);
    if(fd_i == -1)
        err(4, "error while opening file %s", in);

    uint16_t *counting = malloc(0xffff + 1);

    if(counting == NULL) 
        errx(5, "not enough memory");

    uint16_t buf[sizeof(uint16_t) * 1024];

    ssize_t rd_sz;
    while((rd_sz = read(fd_i, &buf, sizeof(buf))) > 0){
        for(uint32_t i = 0; i < rd_sz; ++i){
            ++counting[buf[i]];
        }       
    }

    close(fd_i);

    ssize_t fd_o = open(out, O_CREAT | O_TRUNC | O_RDWR, S_IRUSR | S_IWUSR | S_IRGRP);
    if(fd_o == -1){
        const int _errno = errno;
        close(fd_i);
        free(counting);
        errno = _errno;
        err(6, "error while opening file %s", out);
    }


    size_t MAX = 0xffff + 1;
    size_t pos = 0; // position
    uint32_t i = 0;
    while(i <= MAX){ // iterate over each number
        pos = 0;
        // fill the buffer
        size_t buf_sz = sizeof(uint16_t) * 1024 - 1;
        while(pos < buf_sz && i <= MAX) {   
            if (counting[i] == 0) {
                ++i; // move to next number
            } else {
                buf[pos] = i;
                ++pos;
                --counting[i];
            }
        }

        // write the buffer to the file
        ssize_t wr_sz = write(fd_o, buf, pos);
        if (wr_sz != (ssize_t)pos) {
            err(7, "cannot write %ld bytes to output file", pos);
        }
    }

    close(fd_o);    
    free(counting);
    exit(0);
}

但不幸的是，它给了我分段错误，它不起作用，我不知道为什么:(

4

2 回答 2

1

在这部分

    ssize_t rd_sz;
    while((rd_sz = read(fd_i, &buf, sizeof(buf))) > 0){
        for(uint32_t i = 0; i < rd_sz; ++i){
            ++counting[buf[i]];
        }       
    }

read()您使用了作为元素数量的返回值。
不幸的是，如果读取的字节数是元素数的两倍，read()则会返回什么。 这将导致越界读取。uint16_t

它应该是这样的：

    ssize_t rd_sz;
    while((rd_sz = read(fd_i, &buf, sizeof(buf))) > 0){
        if (rd_sz % sizeof(uint16_t) != 0){
            puts("sorry, partial read not supported!");
            return 1;
        }
        for(uint32_t i = 0; i < rd_sz / sizeof(uint16_t); ++i){
            ++counting[buf[i]];
        }       
    }

缓冲区分配counting也是错误的，因为：

  • 仅分配 0x10000 个字节，而需要 0x10000 个元素（每个元素 2 个字节）（如@MOehm 所说）。
  • 缓冲区在计数之前未初始化。
    uint16_t *counting = malloc(0xffff + 1);

应该

    uint16_t *counting = calloc(0xffff + 1, sizeof(uint16_t));

这样calloc()做：

  • 分配0xffff + 1元素，其大小为sizeof(uint16_t)字节
  • 零初始化分配的缓冲区

还有一点：

size_t MAX = 0xffff + 1;

应该

size_t MAX = 0xffff;

因为你选择使用<=ini <= MAX然后在这里加一个会导致越界读入counting[i]。

于 2020-05-16T10:36:22.167 回答
0

在我添加了所有更正之后，现在分段错误在哪里？

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <stdint.h>
#include <unistd.h>

int main(int argc, char* argv[]) {
    if(argc != 3)
        errx(1, "Usage: %s <input.bin> <output.bin>", argv[0]);

    const char * in = argv[1];
    char * out = argv[2];

    struct stat st;
    if(stat(in, &st) == -1)
        err(2, "fail to stat file %s", in);

    if(st.st_size % sizeof(uint16_t) != 0)
        errx(3, "file %s is corrupted", in);

    if(st.st_size / sizeof(uint16_t) > 0xffff)
        warnx("overflow in file %s may occur", in);

    int fd_i = open(in, O_RDONLY);
    if(fd_i == -1)
        err(4, "error while opening file %s", in);

     uint32_t CMAX = sizeof(uint16_t) * (0xffff + 1); 
    uint16_t *counting = malloc(CMAX);

    if(counting == NULL) 
        errx(5, "not enough memory");

     for(uint32_t i = 0; i < CMAX; ++i){
     counting[i] = 0;
     }

    uint16_t buf[1<<10];

    ssize_t rd_sz;
    while((rd_sz = read(fd_i, &buf, sizeof(buf))) > 0){
        for(uint32_t i = 0; i < rd_sz/sizeof(uint16_t); ++i){
            ++counting[buf[i]];
        }       
    }

    close(fd_i);

    ssize_t fd_o = open(out, O_CREAT | O_TRUNC | O_RDWR, S_IRUSR | S_IWUSR | S_IRGRP);
    if(fd_o == -1){
        const int _errno = errno;
        close(fd_i);
        free(counting);
        errno = _errno;
        err(6, "error while opening file %s", out);
    }


    size_t MAX = 0xffff + 1;
    size_t pos = 0; // position
    uint32_t i = 0;
    while(i <= MAX){ // iterate over each number
        pos = 0;
        // fill the buffer
        while(pos < sizeof(buf) && i < MAX) {   
            if (counting[i] == 0) {
                ++i; // move to next number
            } else {
                buf[pos] = (uint16_t)i;
                ++pos;
                --counting[i];
            }
        }

        // write the buffer to the file
        ssize_t wr_sz = write(fd_o, &buf, pos);
        if (wr_sz != (ssize_t)pos) {
            err(7, "cannot write %ld bytes to output file", pos);
        }
    }

    close(fd_o);    
    free(counting);
    exit(0);
}
于 2020-05-16T13:11:06.880 回答