streaming h264 with rtp

这里记录了使用ffmpeg来发送h264的rtp流,主要问题是处理pps和sps的发送,看了非常多的文档和例子包括gptchat,直到用gdb跟ffmpeg才找到解决办法。

背景

公司的有个发送视频彩铃的业务,需要向终端发送h264。开始想法是创建ffmpeg进程来发送,不过发现进程太好资源并发上不去。后来用写代码来多线程发送。

sdp协商转码问题

sdp协商结果会有不同的分辨率、等级、质量之类的参数(pps/sps),为了避免转码,提前制作了不同参数的视频。不过后来发现只要正确发送pps/sps,终端都能正确解码,不是必须按sdp里的视频参数。

用ffmpeg发送

开始直接使用命令ffmpeg发送,发现终端不能解码。对比正常的rtp流发现缺少了pps/sps。

1
ffmpeg -i video.mp4 -an -c:v copy -f rtp rtp://ip:port

一番搜索发现ffmpeg将pps/sps等参数写到sdp中(out-of-band),还用base64编码了。

1
a=fmtp:96 packetization-mode=1; sprop-parameter-sets=Z2QAKKzRAHgCJ+XAWoCAgKAAAAMAIAAAB4HjBiJA,aOvvLA==; profile-level-id=640028

ffplay等播放软件会解析sdp,载入pps/sps,所以正确解码,但是sip场景下只能通过rtp来发送sps/pps(in-band)。 后来发现用ffmpeg的’bit stream filter’能解决问题

1
ffmpeg -i video.mp4 -an -c:v copy -bsf h264_mp4toannexb -f rtp rtp://ip:port

即使不转码,使用ffmpeg进程发送视频,在两核的系统中大概只能发送十几路。

代码实现发送

基于ffmpeg的示例代码’doc/example/remux.c’, 将原来写文件改为rtp即可。因为还没有用到’h264_mp4toannexb’,还不会发送pps和sps。

关键问题就是如何使用这个bsf

网上看到的例子包括用gptchat生成的例子,都是类似下面的步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 搜索bsf
av_bsf_get_by_name("h264_mp4toannexb")
# 创建bsf的上下文
av_bsf_alloc(bsf, &bsf_ctx)
# 从输入的format上下文中复制编码参数
avcodec_parameters_copy(bsf_ctx->par_in, input_ctx->streams[video_stream_idx]->codecpar)
# 初始化bsf上下文
av_bsf_init(bsf_ctx)
# 读入packet
av_read_frame(input_ctx, &pkt)
# 送到bsf中处理
av_bsf_send_packet(bsf_ctx, pkt)
# 取出处理后的pkt
av_bsf_receive_packet(bsf_ctx, pkt)
# 发送rtp

抓包发现还是没有发送PPS/SPS, 而且第一个NALU是SEI,并且是坏的(Malformed)。调试发现bsf确实成功将SEI从AVCC转换成了AnnexB形式,也在SEI后追加了PPS和SPS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(gdb) x/150bx pkt->data
0x5555556da310: 0x00 0x00 0x00 0x01 0x06 0x05 0x2e 0xdc
0x5555556da318: 0x45 0xe9 0xbd 0xe6 0xd9 0x48 0xb7 0x96
0x5555556da320: 0x2c 0xd8 0x20 0xd9 0x23 0xee 0xef 0x78
0x5555556da328: 0x32 0x36 0x34 0x20 0x2d 0x20 0x63 0x6f
0x5555556da330: 0x72 0x65 0x20 0x31 0x35 0x35 0x20 0x72
0x5555556da338: 0x32 0x39 0x30 0x31 0x20 0x37 0x64 0x30
0x5555556da340: 0x66 0x66 0x32 0x32 0x00 0x80 0x00 0x00
0x5555556da348: 0x00 0x01 0x67 0x64 0x00 0x28 0xac 0xd1
0x5555556da350: 0x00 0x78 0x02 0x27 0xe5 0xc0 0x5a 0x80
0x5555556da358: 0x80 0x80 0xa0 0x00 0x00 0x03 0x00 0x20
0x5555556da360: 0x00 0x00 0x07 0x81 0xe3 0x06 0x22 0x40
0x5555556da368: 0x00 0x00 0x00 0x01 0x68 0xeb 0xef 0x2c
0x5555556da370: 0x00 0x00 0x01 0x65 0x88 0x84 0x02 0xff
0x5555556da378: 0x91 0x3c 0x4a 0x51 0x5b 0xfd 0x02 0x3f
0x5555556da380: 0xc1 0x67 0x8d 0xc0 0x94 0x98 0xee 0x7d
0x5555556da388: 0x43 0x23 0xc0 0x4f 0xf7 0x56 0x37 0xfc
0x5555556da390: 0xf1 0xf3 0xd3 0x83 0x03 0xa9 0x6d 0xd2
0x5555556da398: 0x07 0xcf 0x19 0xa2 0x1e 0x29 0x64 0xfe
0x5555556da3a0: 0x1f 0x8e 0xd6 0x71 0x5f 0x33

0x00 0x00 0x00 0x01是annexb格式的起始码,第一个NALU是0x06(SEI),第二个NALU是0x07(SPS),第三个是0x08(PPS)。问题出在rtp打包的ff_rtp_send_h264_hevc。这里判断出s->nal_length_size不是0而是4, 所以还是以AVCC格式的首四个字节代表长度来解析pkt,而这是pkt是annexB格式了,前四个字节就是0x00, 0x00, 0x00, 0x01。所以打包错误。 问题怎么使rtp按annexB来打包,为什么nal_length_size是4不是0。

1
2
3
4
5
6
7
8
9
10
11
void ff_rtp_send_h264_hevc(AVFormatContext *s1, const uint8_t *buf1, int size)
{
const uint8_t *r, *end = buf1 + size;
RTPMuxContext *s = s1->priv_data;

s->timestamp = s->cur_timestamp;
s->buf_ptr = s->buf;
if (s->nal_length_size)
r = ff_avc_mp4_find_startcode(buf1, end, s->nal_length_size) ? buf1 : end;
else
r = ff_avc_find_startcode(buf1, end);

找到初始化rtp的初始化函数rtp_write_header,发现设置nal_length_size的地方,原来判断extradata,如果第一个字节是1,则按avcc打包。

1
2
3
4
5
6
case AV_CODEC_ID_H264:
/* check for H.264 MP4 syntax */
if (st->codecpar->extradata_size > 4 && st->codecpar->extradata[0] == 1) {
s->nal_length_size = (st->codecpar->extradata[4] & 0x03) + 1;
}
break;

而当前的extradata是类似avcc的(又不同于AVCC, 因为多一个header),第一个字节等于1,而通过调试ffmpeg_g到这里时,extradata是annexB格式,即首4个字节是0x00,0x00,0x00,0x01。关于extradata格式的问题,从开始我就发现刚初始化时,extradata就是0x01开头,那么问题ffmpeg_g的extradata什么时候变的,再次调试发现,bsf初始化跟上面的不同。在ffmpeg_g中bsf初始化在fftools/ffmpeg_mux.c文件中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# fftools/ffmpeg_mux.c
static int bsf_init(MuxStream *ms)
{
OutputStream *ost = &ms->ost;
AVBSFContext *ctx = ms->bsf_ctx;
int ret;

if (!ctx)
return avcodec_parameters_copy(ost->st->codecpar, ost->par_in);

ret = avcodec_parameters_copy(ctx->par_in, ost->par_in);
if (ret < 0)
return ret;

ctx->time_base_in = ost->st->time_base;

ret = av_bsf_init(ctx);
if (ret < 0) {
av_log(ms, AV_LOG_ERROR, "Error initializing bitstream filter: %s\n",
ctx->filter->name);
return ret;
}

ret = avcodec_parameters_copy(ost->st->codecpar, ctx->par_out);
if (ret < 0)
return ret;
ost->st->time_base = ctx->time_base_out;

ms->bsf_pkt = av_packet_alloc();
if (!ms->bsf_pkt)
return AVERROR(ENOMEM);

return 0;
}

发现,ffmpeg的bsf初始化多一个步骤,将bsf的par_out拷贝到输出AVstream中。而这par_out中的extradata就是我们要的annexB格式!

1
ret = avcodec_parameters_copy(ost->st->codecpar, ctx->par_out);

问题找到答案了,1是初始化rtp muxer前先初始化bsf,2是初始化bsf后将par_out拷贝回rtp muxer,再初始化rtp muxer。

正确例子

基于ffmpeg的doc/example/remux.c 删除了错误处理。只关心h264,所以输入输出都只处理index=0的包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int main(int argc, char **argv) {
const AVOutputFormat *ofmt = NULL;
AVFormatContext *ifmt_ctx = NULL, *ofmt_ctx = NULL;
AVPacket *pkt = NULL;
const char *in_filename, *out_filename;
int ret = 0;
in_filename = "video.mp4";
out_filename = "rtp://127.0.0.1:10020";
pkt = av_packet_alloc();
ret = avformat_open_input(&ifmt_ctx, in_filename, 0, 0);
ret = avformat_find_stream_info(ifmt_ctx, 0);
av_dump_format(ifmt_ctx, 0, in_filename, 0);

// 创建输出rtp上下文,不初始化
avformat_alloc_output_context2(&ofmt_ctx, NULL, "rtp", out_filename);
// 初始化bsf
const AVBitStreamFilter *bsf_stream_filter =
av_bsf_get_by_name("h264_mp4toannexb");
AVBSFContext *bsf_ctx = NULL;
ret = av_bsf_alloc(bsf_stream_filter, &bsf_ctx);
ret =
avcodec_parameters_copy(bsf_ctx->par_in, ifmt_ctx->streams[0]->codecpar);
ret = av_bsf_init(bsf_ctx);

ofmt = ofmt_ctx->oformat;
AVStream *out_stream = avformat_new_stream(ofmt_ctx, NULL);
// 关键在这!! 原来是从ifmt_ctx的stream中拷贝codecpar,改成从bsf中拷贝
// ret = avcodec_parameters_copy(out_stream->codecpar, in_codecpar);
ret = avcodec_parameters_copy(out_stream->codecpar, bsf_ctx->par_out);
out_stream->codecpar->codec_tag = 0;
av_dump_format(ofmt_ctx, 0, out_filename, 1);
if (!(ofmt->flags & AVFMT_NOFILE)) {
ret = avio_open(&ofmt_ctx->pb, out_filename, AVIO_FLAG_WRITE);
}
// 初始化bsf后再初始化rtp
ret = avformat_write_header(ofmt_ctx, NULL);

while (1) {
AVStream *in_stream, *out_stream;
ret = av_read_frame(ifmt_ctx, pkt);
if (pkt->stream_index != 0) {
continue;
}
in_stream = ifmt_ctx->streams[pkt->stream_index];
out_stream = ofmt_ctx->streams[pkt->stream_index];
log_packet(ifmt_ctx, pkt, "in");

av_bsf_send_packet(bsf_ctx, pkt);
av_bsf_receive_packet(bsf_ctx, pkt);
/* copy packet */
av_packet_rescale_ts(pkt, in_stream->time_base, out_stream->time_base);
pkt->pos = -1;
log_packet(ofmt_ctx, pkt, "out");
ret = av_interleaved_write_frame(ofmt_ctx, pkt);
}

av_write_trailer(ofmt_ctx);
}

h264_mp4toannexb

这个bsf将从mp4文件中读取的avcc格式的packet转换成annexb格式的packet。调试发现第一个读出来的包是SEI一个I帧,通过bsf处理后,会在SEI后面追加上PPS和SPS信息。而读取mp4文件时,sps/pps在extradata中。

相关知识

这些知识反复看来看去,总也不能贯穿起来,直到问题解决才算明白。

NALU

NALU是真正用来保存h264视频信息的,包括I帧,P/B帧,PPS,SEI,SPS等。NALU由两部分组成:头(1字节)和payload,头中包含nalu的类型。h264规范只定义了NALU本身单元,但没有定义怎么保存NALU单元,所以有了两种格式保存NALU,AVCC和AnnexB。

NALU类型

NAL unit type的值和说明,类型后面跟payload。详细参见在Rec. ITU-T H.264文件的63页,这里展示常用的

  • 5,Coded slice of an IDR picture (I帧)
  • 6,Supplemental enhancement information (SEI)
  • 7,Sequence parameter set (SPS)
  • 8,Picture parameter set (PPS)
  • 24,Single-Time Aggregation Packet(STAP-A)

从抓包看到SPS算上payload的长度为30,PPS算上payload的长度为4。不知道长度是不是固定的。

STAP-A

STAP-A是多个NALU的聚合(Aggregation),即这个NALU的payload里是多个NALU。STAP-A类型的NAL用来发送PPS/SPS/SEI等多种聚合。因为这些单元都很小。STRAP-A类型的header也是一个字节,但是payload里面有多个NALU,并且每个NALU前面用2字节来表示这个NALU的大小。

1
|STAP-A header|NALU-1 size|NALU-1|NALU-2 size|NALU-2|

NALU-1中又有header和payload。

AVCC和AnnexB

上面说了规范没有定义怎么保存NALU,所以有了这两个格式,他们两是平等关系,只有保存的格式不同而已。AVCC用来保存,annexB用来流传输。

  • AVCC用1~4个字节来表示NALU的长度,长度后面是NALU。读取方法是先读长度,再读取NALU。再读下一个长度,再读下一个NALU…
  • 而annexb用0x00,0x00,0x00,0x01或者0x00,0x00,0x01的起始码(start code)来分隔不同的NALU,所以方法是先读起始码,再一直读,直到发现下一个起始码,表示这个NALU结束,下一个NALU开始。

ffmpeg使用中发现,AVCC一般用4字节表示NALU的长度,具体多少字节,在ffmpeg的extradata中有定义。annexB也是用4字节的起始码,也就是0x00,0x00,0x00,0x01。

Fragmentation Units (FUs) 分片

FU就是网络分片,因为I帧是一个完整的图片,所以非常大,为了保证udp不丢包,所以要分次发送。 第一个分片的FU的头设置了Start bit, 最后一个分片的FU头设置了END bit。分片是在rtp muxer中完成,注意ffmpeg中一个packet可以包含多个音频帧,但是只包含一个帧,直到发送rtp之前,一个packet总是完整的一帧视频(I/P/B)。 对于比较小的packet,例如聚合了PPS/SPS等信息的STAP-A包,不需要分片。

extradata

上面很多次提到ffmpeg的extradata, 就是AVCodecParameters.extradata,它的长度是AVCodecParameters.extradata_size。在读取mp4文件的时候,ffmpeg会自动填充,在解码rtp的时候可能就需要手动填充了。extradata的比特位如下,首先是6字节的头,然后是多个SPS类型的NALU(2字节的长度分割多个NALU),再然后是PPS类型的NALU个数,最后是PPS类型的多个NALU(2字节的长度分割多个NALU)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bits    
8 version ( always 0x01 )
8 avc profile ( sps[0][1] )
8 avc compatibility ( sps[0][2] )
8 avc level ( sps[0][3] )
6 reserved ( all bits on )
2 NALULengthSizeMinusOne
3 reserved ( all bits on )
5 number of SPS NALUs (usually 1)

repeated once per SPS:
16 SPS size
variable SPS NALU data

8 number of PPS NALUs (usually 1)

repeated once per PPS:
16 PPS size
variable PPS NALU data

里面包含了一个或多个PPS/SPS(NALU),但保存的格式,既不是AVCC也不是AnnexB。因为上面可知AVCC用14个字节表示NALU的长度,AnnexB用34字节的起始码,而extradata是有一个6字节的header,里面有个字段叫NALULengthSizeMinusOne就是定义了AVCC使用多少个字节来表示NALU的长度。如果NALULengthSizeMinusOne等于0,那么AVCC用1字节表示NALU的长度。通常就是用4字节。

extradata例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(gdb) x /150bx fmt_ctx->streams[0]->codecpar->extradata
0x55555571d9c0: 0x01 0x64 0x00 0x28 0xff 0xe1 0x00 0x1e
0x55555571d9c8: 0x67 0x64 0x00 0x28 0xac 0xd1 0x00 0x78
0x55555571d9d0: 0x02 0x27 0xe5 0xc0 0x5a 0x80 0x80 0x80
0x55555571d9d8: 0xa0 0x00 0x00 0x03 0x00 0x20 0x00 0x00
0x55555571d9e0: 0x07 0x81 0xe3 0x06 0x22 0x40 0x01 0x00
0x55555571d9e8: 0x04 0x68 0xeb 0xef 0x2c 0x00 0x00 0x00
0x55555571d9f0: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571d9f8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da00: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da08: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da10: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da18: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da20: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da28: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da30: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da38: 0xc1 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x55555571da40: 0x9d 0xad 0x00 0x00 0x50 0x55 0x00 0x00
0x55555571da48: 0xfa 0x19 0xc4 0x92 0x40 0xa0 0xdc 0xba
0x55555571da50: 0x00 0x00 0x00 0x00 0x00 0x00
  • 第5字节0xff,二进制为:1111 1111, 后2位表示NALULengthSizeMinusOne=3,所以ffmpeg用4字节表示NALU的大小(AVCC格式)。
  • 第6字节0xe1,二进制为:1110 0001,后5位表示SPS的个数=1,所以只有一个SPS。
  • 第7,8字节表示SPS的长度,0x00,0x1e,二进制为:0000 0000, 0001 1110,所以SPS长度为30。
  • 跳过30个字节,0x01,二进制为:0000 0001, 表示有1个PPS。
  • 后面的2个字节,0x00,0x04,二进制为:0000,0004,表示PPS的长度为4个字节。
NALU头的解析

NALU头是1字节,第一位F bit, 后两位NRI bit, 后五位表示NALU的type。

SPS的头是0x67,而进制为: 01100111,所以type值正好是7。
PPS的头是0x68,而进制为: 01101000,所以type值正好是8。

对比wireshark解析结果可以确认上面的理解正确,可见extradata就是6个字节的header加多个AVCC格式的NALU。

创建extradata

rtp解码时,需要手动生成extradata。创建AVCC格式的extradata

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
write(0x1);  // version
write(sps[0].data[1]); // profile
write(sps[0].data[2]); // compatibility
write(sps[0].data[3]); // level
write(0xFC | 3); // reserved (6 bits), NULA length size - 1 (2 bits)
write(0xE0 | 1); // reserved (3 bits), num of SPS (5 bits)
write_word(sps[0].size); // 2 bytes for length of SPS
for(size_t i=0 ; i < sps[0].size ; ++i)
write(sps[0].data[i]); // data of SPS

write(&b, pps.size()); // num of PPS
for(size_t i=0 ; i < pps.size() ; ++i) {
write_word(pps[i].size); // 2 bytes for length of PPS
for(size_t j=0 ; j < pps[i].size ; ++j)
write(pps[i].data[j]); // data of PPS
}

创建annexB格式的extradata

1
2
3
4
5
6
7
8
9
10
11
12
13
14
write(0x00)
write(0x00)
write(0x00)
write(0x01)
for each byte b in SPS
write(b)

for each PPS p in PPS_array
write(0x00)
write(0x00)
write(0x00)
write(0x01)
for each byte b in p
write(b)

wireshark解析

从wiresshark对比用bsf和不用bsf的抓包发现,SEI包的内容没有变化,是不是可以不需要转成annexb,直接将PPS/SPS直接拷贝到packet中发出去呢?

参考

https://membrane.stream/learn/h264/3
https://github.com/cisco/openh264/issues/2501#issuecomment-231340268
https://stackoverflow.com/questions/17667002/how-to-add-sps-pps-read-from-mp4-file-information-to-every-idr-frame
https://stackoverflow.com/questions/24884827/possible-locations-for-sequence-picture-parameter-sets-for-h-264-stream
https://aviadr1.blogspot.com/2010/05/h264-extradata-partially-explained-for.html

随身wifi工具

本文记录了淘宝卖的随身wifi刷机成Debian,还能收发短信。还有救砖的艰辛过程,不过结局美满。

依赖

切卡

刚接触时看网上的都是在后台页面切卡,但是刷机了没有后台页面如何切卡呢? 为了切卡又重刷安卓,导致变砖了。参考网上资料发现,Debian下可以直接切。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
debian默认卡槽位1:

echo 1 > /sys/class/leds/sim:sel/brightness
echo 0 > /sys/class/leds/sim:en/brightness
echo 0 > /sys/class/leds/sim:sel2/brightness
echo 0 > /sys/class/leds/sim:en2/brightnessR
modprobe -r qcom-q6v5-mss
modprobe qcom-q6v5-mss
systemctl restart rmtfs
systemctl restart dbus-org.freedesktop.ModemManager1.service

esim槽位3:

echo 0 > /sys/class/leds/sim:sel/brightness
echo 0 > /sys/class/leds/sim:en/brightness
echo 1 > /sys/class/leds/sim:sel2/brightness
echo 0 > /sys/class/leds/sim:en2/brightness
modprobe -r qcom-q6v5-mss
modprobe qcom-q6v5-mss
systemctl restart rmtfs
systemctl restart dbus-org.freedesktop.ModemManager1.service

其他两个槽位

槽位2:

echo 0 > /sys/class/leds/sim:sel/brightness
echo 1 > /sys/class/leds/sim:en/brightness
echo 0 > /sys/class/leds/sim:sel2/brightness
echo 0 > /sys/class/leds/sim:en2/brightness
modprobe -r qcom-q6v5-mss
modprobe qcom-q6v5-mss
systemctl restart rmtfs
systemctl restart dbus-org.freedesktop.ModemManager1.service

槽位4:
echo 0 > /sys/class/leds/sim:sel/brightness
echo 0 > /sys/class/leds/sim:en/brightness
echo 0 > /sys/class/leds/sim:sel2/brightness
echo 1 > /sys/class/leds/sim:en2/brightness
modprobe -r qcom-q6v5-mss
modprobe qcom-q6v5-mss
systemctl restart rmtfs
systemctl restart dbus-org.freedesktop.ModemManager1.service

有些棒子esim槽位不一样槽位3不行自行试试槽位2 4

https://github.com/OpenStick/OpenStick/issues/49#issuecomment-1568202001

刷机

先使用edl全量备份,方法在最下面。先刷base包,解压base.zip后执行里面的flash.sh。然后刷debian包,解压debian.zip后执行里面的flash.sh。这时进入系统发现可能出现问题(我也没明显感觉到问题),因为他们是ufi001b的。
所以再刷适配ufi001c的包,解压firmware-ufi001c.zip。

1
2
3
4
5
cd firmware-ufi001c
adb push ./* /lib/firmware
adb reboot bootloader
fastboot flash boot boot-ufi001c.img
fastboot reboot

但是在刷ufi001c的包之前我能找到modem网络,刷完就没了,所以有了下面基带恢复的步骤。

基带

基带文件在随身wifi的modem分区,先用edl备份modem分区。当然下面介绍了edl全量备份,跳过了userdata,估计是root和home目录。

恢复基带文件

我在安装debian系统时,发现移动网络不可用,于是参考网上说的,将原始基带恢复后正常。 基带文件名为”modem.bin”, edl全量备份后在dumps目录下。直接mount该文件,然后将modem.*和mba.mbn取出来,当发现刷机后发现移动网络不能使用时,重新拷回去就能用了。

1
sudo mount modem.bin /mnt

复制到firmware-ufi001c目录,覆盖之前的文件。

1
2
cp /mnt/modem.* .
cp /mnt/mba.mbn .

再次拷贝到wifi棒子的/lib/firmware目录, 配合再刷一次适配001C的boot文件。

1
2
3
4
adb push ./* /lib/firmware
adb reboot bootloader
fastboot flash boot boot-ufi001c.img
fastboot reboot #重启

然后就能找到modem网卡了。

重启modem

有时重刷了firmware,还是出现没有modem网卡的情况,也就是mmcli -m 0提示找不到modem设备的时候,需要执行下面的命令。或者直接等一会重启ModemManager

1
2
3
systemctl stop ModemManager
qmicli -d /dev/wwan0qmi0 --uim-sim-power-off=1 && qmicli -d /dev/wwan0qmi0 --uim-sim-power-on=1
systemctl start ModemManager

短信收发和转发邮件

下载两个python文件,地址 https://gitee.com/jiu-xiao/ufi-message。配置smtp.py中的邮箱信息,我使用的QQ邮箱登录,然后转发到另一个邮箱。开始发送不成功,修改后能发送了,内容如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!python3

my_sender='@qq.com'
my_user='@hotmail.com'
server_address='smtp.qq.com'
server_port=465
server_passwd='' #填写qq邮箱授权码


import smtplib
from email.mime.text import MIMEText
from email.utils import formataddr
import datetime
import time

def mail(text):
msg=MIMEText(text,'plain','utf-8')
msg['From']=formataddr(["随身Wifi",my_sender])
msg['To']=formataddr([my_user,my_user])
msg['Subject']="转发 "+time.strftime("%H:%%M:%S %m/%d")

server=smtplib.SMTP_SSL(server_address,server_port)

server.login(my_sender,server_passwd)
server.auth_plain()
server.sendmail(my_sender,[my_user,],msg.as_string())
server.quit()

然后就能写进crontab自动跑了。

救砖

edl使用

github上的开源工具,可以替代Windows那些高通工具,Miko,星海啥的。是我这Linux用户的福音,并且简单,windows常常失败。
使用edl工具之前要先重启到edl也就是9008模式,使用命令adb reboot edl,不需要按RST键。

备份:推荐第一种方式,第二种方式生成的一个文件刷到另一个设备失败,但是可以刷MiKo导出的单文件。

1
2
3
edl rl dumps --skip=userdata --genxml
or
edl rf flash.bin #单文件

恢复:

1
edl qfil rawprogram0.xml patch0.xml .

恢复分区

刷了debian后,分区会变,这样导致有些分区不存在所以无法刷回去。这里介绍下恢复分区的方法。不过上面的edl恢复应该不需要这个操作。

备份分区

1
./edl gpt . --genxml

备份后有两个文件,恢复时只用gpt_main0.bin文件,恢复分区命令

1
./edl w gpt gpt_main0.bin

打印分区来验证下

1
./edl printgpt

参考

https://forum.openwrt.org/t/uf896-qualcomm-msm8916-lte-router-384mib-ram-2-4gib-flash-android-openwrt/131712/160
https://www.kancloud.cn/handsomehacker/openstick/2636505

docker network

记录一次docker的网络问题,以及学到的知识。

背景

公司用docker容器替代虚拟机来隔离,用来ssh登录以及运行不同的服务。容器连接了双网络,一个用来访问同宿主机上的容器,另一个用来从其他主机访问。

问题

宿主机重启之后,容器无法访问。需要手动改路由。

解决办法

每次修改路由麻烦,后面发现两个网络都是macvlan时,存在无法没有网络。

创建桥接物理网卡

这是需要指定parent为物理网卡,既然是桥接物理网卡,就能从其他宿主机访问了。

1
docker network create -d bridge   --subnet=10.9.3.0/24   --gateway=10.9.3.1   -o parent=ens39f0 public_net_bridge
1
docker network create -d macvlan  --subnet=10.9.3.0/24   --gateway=10.9.3.1   -o parent=ens39f0 public_net_macvlan

这两个由于使用的同一个网段/网卡,所以不可能同时存在。也许可以通过指定不同的ip-range来实现吗?

创建桥接虚拟网卡

这种网络就不能从非宿主机的其他主机访问,只能在同宿机下的容器之间访问。我称之为私有网络

1
docker network create -d bridge   private_net_bridge
1
docker network create -d macvlan  private_net_macvlan

这里没有指定网络地址

iperf测速

发现无论桥接物理网卡还是虚拟网卡,macvlan都要比bridge快

  • 私有网络
    bridge 模式分别测得: 20.4 Gbits/sec 22.6 Gbits/sec 23.0 Gbits/sec
    macvlan 模式分别测得: 26.1 Gbits/sec 24.4 Gbits/sec 26.7 Gbits/sec

  • 桥接物理网卡
    macvlan: 25.7 Gbits/sec 25.5 Gbits/sec 27.3 Gbits/sec
    bridge: 20.2 Gbits/sec 20.4 Gbits/sec 23.2 Gbits/sec

顺便说下容器连接多网络的方法

容器启动的时候,只能指定一个网络, 然后启动之后,可以通过命令来连接多网络,可以在启动时设置–restart=alway,这样重启主机后自动连接双网络

1
docker network connect private_net_bridge test_container

杂项

网络配置挺复杂,macvlan 下面还分

  • Bridge mode, 就是常见的模式,走宿主机的网卡
  • 802.1q trunk bridge mode, 先在物理网卡上创建子网卡

IPvlan

除了bridge macvlan之外,还有IPvlan, 这种模式下,所有的容器都使用相同的mac地址,所以如果容器使用dhcp来获取ip地址,则可能有问题。 访问其他容器时,可以配置来使用macvlan模式。

overlay

docker network driver 除了上面的三种模式之外,还有overlay, 用于连接不同主机的网络,可以跨宿主机访问容器。

宿主机网络类型

我通常会创建bridge并将物理网卡设为从卡,然后创建虚拟网桥,用于访问虚拟机。而除了bridge, 还有bond,另外还有team。总而言之,bridge可以使不同的虚拟机(client)使用网卡的虚拟化功能,而bond可以将不同的网卡绑定,实现负载均衡。如果两个网卡分别有1M带宽,那么bond后的网卡则有2M带宽。下面的链接先bonding,然后在bonding网卡上创建bridge网卡。参考

mail setup

Linux下的邮件配置

这里记录Linux(debian)下如何使用Mutt查看邮件,用fetchmail接收邮件,用msmtp发送邮件以及使用maildrop来筛选邮件。与其他邮件客户端相比,如thunderbird,他们使用的在线登陆方式,没有下载邮件来离线访问。而mutt支持离线访问本地的邮件,也可以配置为访问邮件服务器,查看服务器上的邮件。 在线方式除了离线不可用的缺点之外,每次打开mutt需要登陆,非常慢。
我这里的配置是比较简陋,适合公司少量邮件的场景。又因为目前使用的Byobu-terminal终端,其邮件提醒是基于/var/mail/spool/$USER文件。邮件比较多或者附件比较大的话,相较于用文件夹来存储邮件,这种方式会比较慢。

软件安装

需要安装 fetchmail, maildrop, mutt

接收配置

在家目录下创建文件.fetchmailrc

1
2
3
4
5
6
7
8
9
10
poll imap.exmail.qq.com
protocol IMAP
user "example@example.com"
password "password"
keep
#fetchall
ssl

mimedecode
mda "/usr/bin/maildrop"

keep 方式不会删除服务器上的邮件。然后启动定时任务,自动检查新邮件

1
systemctl --user enable --now fetchmail.service

发送配置

在家目录创建文件.msmtproc,填入发送的验证信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
defaults
auth on
tls on
tls_starttls off
tls_trust_file /etc/ssl/certs/ca-certificates.crt
logfile ~/.msmtp.log

# exmail
account office
host smtp.exmail.qq.com
port 465
from example@example.com
user example@example.com
password password

mutt配置

由于我不想删除/var/mail/里面的邮件,这样才能在byobu-terminal中提醒,所以没有配置maildrop。最后需要配置mutt读取/var/mail/$USER。在家目录或者xdg配置目录(~/.config/mutt)创建文件.muttrc/muttrc

1
2
3
set spoolfile=/var/spool/mail/jimery
set header_cache=~/.cache/mutt
set send_charset="utf-8"

这样就能查看邮件了。 在mutt里面手动管理邮件,存档或者删除。

mutt使用

其实不用mutt, 直接用mail也可以,这个默认访问/var/mail/$USER,是Linux默认的邮件工具。 mutt能很方便调用msmtproc来发送邮件。

install wordpress

安装wordpress记录

本文记录在debian上安装配置wordpress的补助,并配置了ftp功能,支持自更新wordpress。

安装wordpress

下载最新的包,解压到/var/www/html

安装配置数据库

安装mariadb, 创建数据库和用户

1
2
3
4
mysql -u root
CREATE DATABASE wordpressdb;
CREATE USER wordpressuser@localhost IDENTIFIED BY 'password';
GRANT ALL PRIVILEGES ON wordpressdb.* TO wordpressuser@localhost;

安装配置nginx php

安装nginx和php-7.4,还有php一些组件
nginx 配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
server { 
listen 80 default_server;
listen [::]:80 default_server;
server_name your_domain.com;

root /var/www/html;
index index.php index.html index.htm;

location / {
# try_files $uri $uri/ =404;
try_files $uri $uri/ /index.php?q=$uri&$args;
}

location ~ \.php$ {
include snippets/fastcgi-php.conf;
fastcgi_split_path_info ^(.+\.php)(/.+)$;
fastcgi_pass unix:/run/php/php-fpm.sock;
}
}

安装配置vsftpd

安装后,修改配置文件/etc/vsftpd.conf

1
2
3
4
5
6
7
local_enable=YES
write_enable=YES
chroot_local_user=YES
chroot_list_enable=YES
chroot_list_file=/etc/vsftpd.chroot_list
allow_writeable_chroot=YES
pm_service_name=ftp

添加用户,并限制权限

1
2
3
4
5
6
7
8
useradd [user_name]
passwd [user_name]
usermod -d /var/www/html/wordpress user_name -s /sbin/nologin

setfacl -m u:ftpsecure:r-x /var/www/html/

setfacl -R -m u:ftpsecure:rwx /var/www/html/wordpress
setfacl -R -d -m u:ftpsecure:rwx /var/www/html/wordpress

如果提示没有setfacl命令,则执行安装acl命令 apt install acl

ftp遇到问题和解决办法

  • 登陆提示”500 OOPS: could not read chroot() list file:/etc/vsftpd.chroot_list”,需要创建文件/etc/vsftpd.chroot_list

  • 登陆ftp报530验证失败的问题,修改配置如下

    1
    pm_service_name=ftp
  • 登陆提示”500 OOPS: vsftpd: refusing to run with writable root inside chroot()

1
allow_writeable_chroot=YES
  • 登陆提示 500 OOPS: vsftpd: refusing to run with writable root ,意思是登陆者具备对目录的写权限,这是由于目录设定权限为777,所以要是重新设定为755
    1
    chmod 755 /srv/ftp

配置wordpress

修改wordpress/wp-config.php 文件, 添加如下内容

1
2
3
define('FTP_HOST', 'localhost');
define('FTP_USER', 'ftp');
define('FTP_PASS', '');

通过wordpress的api可以生成随机token,将输出替换到wordpress/wp-config.php

1
2
3
4
5
6
7
8
9
10
$curl -s https://api.wordpress.org/secret-key/1.1/salt/

define('AUTH_KEY', 'uOeyPW$K[P}23x^0l##N+qP#xzUlIBV[ZQlATs!7J?+5^!w0*bgEw|V6)k:YU0en');
define('SECURE_AUTH_KEY', 'Ad*-`eK|U4Z*7g}7CdX<q0^EuGqT1Tt}CaDRgF%NX-|fmk(:BACtws+^_0Pb8ZRA');
define('LOGGED_IN_KEY', ':Z$}=h~z-[]8W}wZ(|/;]ZY;U{>u3K>P|u6/d:6}&h*);0ewhrcGm8$/tPii#{,%');
define('NONCE_KEY', 'd}Ue8.+KPDGdH^%2t~fTljDj8e{q{raR!Q0piqM(gcQP&7-$L3u0u|!Bn(-gh/?B');
define('AUTH_SALT', 'UQh.k>4UBTK6IecZe~lL6|J/w^KFROIeCdZw^g=(x?(L+j(-|%C FCt =V*XVz+k');
define('SECURE_AUTH_SALT', 'hHr&dDCApb14yz@ks+;}mk,s<-[]KUj*UAhl0+<pqT*!j;wxc+[mU[czh =><#em');
define('LOGGED_IN_SALT', 'WO,U^A||&:E@2A2_|MS W1l`fguj-7E{Fz6QkC+OM96Ho49<agM?O=G2FloxuF?6');
define('NONCE_SALT', 'uDN.1::MJ>~9Yp+e39y%o?r >:+OcUSqg5_g<Jt:Sr!um?U:U|MJ2q2qKiLDfmr@');

更新数据库配置到wp-config.php

更新url

开始使用http访问,后面切换到https后一直提示错误说跳转太多次。后来发现原因是套了cloudflare,cloudflare设置的是前端https后端http, 后端以http访问真实服务器后又跳转到https。所以请求一直在cf<->wordpress之间无限跳转。所以首先要设置cloudflare的代理模式为严格安全,strict full safe,也就是前端和后端都用证书。然后修改wordpress的url方法有很多,之前通过直接修改数据库,这次发现wordpress有个wp的命令行工具,一键修改。

vsftpd 配置默认目录

为local user配置默认目录,例如所有用户登录后进入/home目录, 添加配置local_root=/home,为匿名用户配置默认目录为tmp目录,则添加配置anon_root=/tmp

参考

https://serverfault.com/questions/544850/create-new-vsftpd-user-and-lock-to-specify-home-login-directory
https://shiftedbits.org/2012/01/29/enable-wordpress-automatic-updates-on-a-debian-server/

amrnb和amrwb的编解码

目的

最近在公司开发一个amrnb/amrwb的转码工具,在网上看了很多资料,主要是这篇AMR在IP域中的编码(rfc3267,4867) 对我帮助很大。 这里补充一下缺少和我自己的理解。

AMR编码介绍

AMR是3GPP组织的一个音频编码规范,目前的手机都使用AMR, 比如公司的测试机华为、小米只支持amrnb/amrwb。amrnb是对窄带信号进行编码(200–3400 Hz),amrwb是对更宽的频率范围进行编码(50–7000 Hz)。
根据香农理论,采样频率要是目标频率的两倍,所以向上取整的amrnb的采样频率是8000Hz, amrwb的采样频率是16000Hz。

bitrate

amrnb和amrwb有多种编码速率(bitrate),并支持在通话过程中通过CMR(codec mode request)协商来变化编码速率,不同于一般的编码器固定一种比特率。除此之外,还有没有人声时的SID(舒适噪音)模式。这时只需要发送一个Mode而不是发送无声的包,从而来降低带宽占用。

amrnb 不同比特率时的语音帧大小

Index Mode Class A bits total speech bits
0 4.75 42 95
1 5.15 49 103
2 5.9 55 118
3 6.7 58 134
4 7.4 61 148
5 7.95 75 159
6 10.2 65 204
7 12.2 81 244

amrwb 不同比特率的语音帧大小

Index AMR-WB codec mode Total number of bits Class A Class B Class C
0 6.60 132 54 78 0
1 8.85 177 64 113 0
2 12.65 253 72 181 0
3 14.25 285 72 213 0
4 15.85 317 72 245 0
5 18.25 365 72 293 0
6 19.85 397 72 325 0
7 23.05 461 72 389 0
8 23.85 477 72 405 0

payload type

amrnb和amrwb使用的动态payload type, 所以在用wireshark分析时,需要经常调整payload-type值

align mode

amrnb和amrwb在SIP协商中有两种align mode,对齐模式和节省带快模式。总结有几个区别

  • 对齐模式下CMR占8位,每个TOC占8位,然后每个语音帧补齐为整字节。
  • 节省带宽模式下,CMR占4位,每个TOC占6位,然后CMR + TOC + 所有语音帧加起来,最后补齐为整字节。

以单帧的12.2kbps为例

  • 语音帧为244位,对齐之后为(244 + 8 - 1)/8 = 31字节。加上1字节的CMR和1字节的TOC, 一共33字节。
  • 语音帧为244位,加上4位CMR和6位TOC,一共为254位,对齐后为(254 + 8-1)/8,一种32字节字节。

以两帧的12.2kbps为例

  • 两个语音帧分别占用31字节,加上1字节的CMR和2字节的TOC, 一共 65字节。
  • 两个语音帧分别占用244位, 加上4位的CMR和6 * 2位的TOC, 对齐后为( 488 + 4 + 12 + 8 - 1)/8,一共63字节。

总之,对齐模式是先对齐成字节再求和,节省带宽模式是先计算位和再对齐成字节。特别是多帧的时候,节省带宽模式算起来更复杂。好在实际情况都是1帧。

基于opencore-amr的编解码

开始用FFmpeg的库来做转码和推流,后来发现不支持节省带宽模式,而且还有个BUG,所以后面自己基于opencore的库写的转码功能。

use mdns in systemd-networkd

使用systemd-resolved的mdns

之前的博客中使用了avahi来广播本机的hostname和服务,这对于打印机和其他无屏设备非常重要。而较新版本Linux发行版中systemd-networkd+systemd-resolved同样能实现此功能

Network Manager

目前不少发行版默认的网络管理工具是NetworkManager, 需要先将其关闭和卸载,安装systemd-networkd包

配置systemd-networkd

networkd 中可以配置网桥,tun等设备,也可以直接在其中配置dns和dhcp等,在其中加入MulticastDNS=yes和Multicast=yes来启用mDns

1
2
3
4
5
6
7
8
9
10
11
[Match]
Name=eth0

[Network]
Address=192.168.4.42/24
DNS=114.114.114.114
Gataway=192.168.4.1
MulticastDNS=yes

[Link]
Multicast=yes

配置systemd-resolved

systemd-resolved功能类似与dnsmasq, 他会继承systemd-networkd中的dns信息,也会读取hostname用来广播,一般不用修改任何配置,之需要将其stub文件链接到/etc/resov.conf, 这样让系统的dns请求发到systemd-resolved

1
2
3
# ln -sf /run/systemd/resolve/stub-resolv.conf /etc/resolv.conf
# ls -l /etc/resolv.conf
lrwxrwxrwx. 1 root root 37 May 22 22:03 /etc/resolv.conf -> /run/systemd/resolve/stub-resolv.conf

确认效果

通过resolvectl status命令可以查看resolve配置,如下全局的MulticastDNS是启用的,而networkd中的配置是per link的,也处于启用状态,Scopes里显示了mDNS,说明其启用了

1
Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6 mDNS/IPv4 mDNS/IPv6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
[root@netpanc ~]# resolvectl status
Global
LLMNR setting: yes
MulticastDNS setting: yes
DNSOverTLS setting: no
DNSSEC setting: allow-downgrade
DNSSEC supported: yes
DNSSEC NTA: 10.in-addr.arpa
16.172.in-addr.arpa
168.192.in-addr.arpa
17.172.in-addr.arpa
18.172.in-addr.arpa
19.172.in-addr.arpa
20.172.in-addr.arpa
21.172.in-addr.arpa
22.172.in-addr.arpa
23.172.in-addr.arpa
24.172.in-addr.arpa
25.172.in-addr.arpa
26.172.in-addr.arpa
27.172.in-addr.arpa
28.172.in-addr.arpa
29.172.in-addr.arpa
30.172.in-addr.arpa
31.172.in-addr.arpa
corp
d.f.ip6.arpa
home
internal
intranet
lan
local
private
test

Link 2 (eth0)
Current Scopes: DNS LLMNR/IPv4 LLMNR/IPv6 mDNS/IPv4 mDNS/IPv6
LLMNR setting: yes
MulticastDNS setting: yes
DNSOverTLS setting: no
DNSSEC setting: allow-downgrade
DNSSEC supported: yes
Current DNS Server: 114.114.114.114
DNS Servers: 114.114.114.114

在其他设备上ping可以成功

1
2
3
4
PING netpanc.local (192.168.4.43) 56(84) bytes of data.
64 bytes from netpanc.local (192.168.4.43): icmp_seq=1 ttl=64 time=0.350 ms
64 bytes from netpanc.local (192.168.4.43): icmp_seq=2 ttl=64 time=0.799 ms
64 bytes from netpanc.local (192.168.4.43): icmp_seq=3 ttl=64 time=0.733 ms

参考

https://wiki.archlinux.org/title/Systemd-resolved#mDNS

序列化和反序列化

定义

c/c++中,序列化是将基本类型或struct变为可存储和传递的形式,比如常用的socket send,将按协议组装的struct(pack)显示转换二进制(序列化)并发送给其他主机。而反序列化是将二进制转成基本类型或struct。另外还有fwrite/fread将结构体保存到文本中。 这种方式高效但容易出错。
而其他语言中可以使用xml, json等高级方式

转换方式

强制类型转换

上面讲到的两个函数send和fwrite,都是将基本类型或struct类型强转为字符串, 这种可能受不同机器的对齐影响

1
2
3
4
ssize_t send(int sockfd, const void *buf, size_t len, int flags);

size_t fwrite(const void *ptr, size_t size, size_t nmemb,
FILE *stream);

序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct buffer {
int a;
char b;
double c;
};

int main() {

struct buffer buf;
buf.a = 1;
buf.b = 'a';
buf.c = 2;

FILE *f = fopen("/tmp/buf", "w+");
if (f == NULL) {
return 1;
}
fwrite(&buf, sizeof(struct buffer), 1, f);
}

反序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct buffer {
int a;
char b;
double c;
};

int main() {

struct buffer buf;

FILE *f = fopen("/tmp/buf", "r");
if (f == NULL) {
return 1;
}

fread(&buf, sizeof(struct buffer), 1, f);
printf("%d--%c--%lf--\n", buf.a, buf.b, buf.c);
}

使用protobuf

1
2
3
4
5
6
7
8
9
syntax = "proto3";
package serialize;

option optimize_for = LITE_RUNTIME;

message Person {
string name = 1;
int32 id = 2;
}
1
2
3
4
5
6
7
8
9
10
11
tutorial::Person Serialize(std::string name, int id, std::string email){
tutorial::Person person;
person.set_name(name);
person.set_id(id);

return person;
}

void Deserialize(tutorial::Person person){
std::cout << person.SerializeAsString();
}

optimize_for option

optimize_for (file option): Can be set to SPEED, CODE_SIZE, or LITE_RUNTIME. This affects the C++ and Java code generators (and possibly third-party generators) in the following ways:

  • SPEED (default): The protocol buffer compiler will generate code for serializing, parsing, and performing other common operations on your message types. This code is highly optimized.
  • CODE_SIZE: The protocol buffer compiler will generate minimal classes and will rely on shared, reflection-based code to implement serialialization, parsing, and various other operations. The generated code will thus be much smaller than with SPEED, but operations will be slower. Classes will still implement exactly the same public API as they do in SPEED mode. This mode is most useful in apps that contain a very large number of .proto files and do not need all of them to be blindingly fast.
  • LITE_RUNTIME: The protocol buffer compiler will generate classes that depend only on the “lite” runtime library (libprotobuf-lite instead of libprotobuf). The lite runtime is much smaller than the full library (around an order of magnitude smaller) but omits certain features like descriptors and reflection. This is particularly useful for apps running on constrained platforms like mobile phones. The compiler will still generate fast implementations of all methods as it does in SPEED mode. Generated classes will only implement the MessageLite interface in each language, which provides only a subset of the methods of the full Message interface.

其他还有如xml, json, ninja

背包问题

背包问题

有一个承重为V的背包,有N个物品,重量分别为Cost[i], 价值分别为Value[i], 问选择放哪些物品时包的价值最大

状态方程

解决动态编程的关键是找到状态方程,如下。 解决背包问题就是比较不放哪个价值高

1
F [i, v] ← max{F [i − 1, v], F [i − 1, v − Ci] + Wi}

01背包

要求物品最大为1个, 这里有几个版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <sys/param.h>

const int V = 4, N = 3;
const int cost[N] = {1, 3, 4};
const int value[N] = {15, 20, 30};

// const int V = 10, N = 5;
// const int cost[N] = {2, 3, 5, 2, 4};
// const int value[N] = {2, 2, 1, 1, 2};

void O1Package_N() {
int dp[N][V + 1];

// 0容量的价值为0, 合法
for (int i = 0; i <= V; i++) {
dp[0][i] = 0;
}

// 初始化当包承重大于物品0重量的情况
for (int j = cost[0]; j <= V; j++) {
// 当只装物品0时,包的价值就是物品0的价值
dp[0][j] = value[0];
}

// 先遍历物品,后遍历重量
for (int i = 1; i < N; i++) {
for (int v = 0; v <= V; v++) {
// F [i, v] ← max{F [i − 1, v], F [i − 1, v − Ci] + Wi}
// F[i][v] = MAX(F[i - 1][v], F[i - 1][v - cost[i]] + value[i]);
int bufang = dp[i - 1][v];
dp[i][v] = bufang;
if (v >= cost[i]) {
int fang = dp[i - 1][v - cost[i]] + value[i];
dp[i][v] = MAX(bufang, fang);
}
}
}

for (int i = 0; i < N; i++) {
for (int j = 0; j <= V; j++) {
printf("%d\t", dp[i][j]);
}
printf("\n");
}
printf("%d\n", dp[N - 1][V]);
}

void O1Package_N_plus_1() {

int dp[N + 1][V + 1];

// 使用0个物品的价值为0
for (int i = 0; i <= V; i++) {
dp[0][i] = 0;
}

// 先遍历物品,后遍历重量
for (int i = 1; i <= N; i++) {
for (int v = 0; v <= V; v++) {
dp[i][v] = dp[i - 1][v]; //当重量不够装i时,价值为装i-1的价值,
//此步骤以备i+1时使用(下一个i循环)
if (v >= cost[i - 1]) {
dp[i][v] = MAX(dp[i - 1][v], dp[i - 1][v - cost[i - 1]] + value[i - 1]);
}
}
}

for (int i = 0; i <= N; i++) {
for (int j = 0; j <= V; j++) {
printf("%d\t", dp[i][j]);
}
printf("\n");
}
printf("%d\n", dp[N][V]);
}

void O1Package_N_plus_1_origin() {

int dp[N + 1][V + 1];

// 使用0个物品的价值为0
for (int i = 0; i <= V; i++) {
dp[0][i] = 0;
}

// 先遍历物品,后遍历重量
for (int i = 0; i < N; i++) {
for (int v = 0; v <= V; v++) {
// 1. 当物品大于承重,物品不会放到背包,价值等于不放此物品时的情况
// 即使物品小于承重,说明物品会放到背包。提前多赋值一次也是允许的
dp[i + 1][v] = dp[i][v];
if (v >= cost[i]) {
dp[i + 1][v] = MAX(dp[i][v], dp[i][v - cost[i]] + value[i]);
}
}
}

for (int i = 0; i <= N; i++) {
for (int j = 0; j <= V; j++) {
printf("%d\t", dp[i][j]);
}
printf("\n");
}
printf("%d\n", dp[N][V]);
}

void O1Package_one_array_n() {

int dp[V + 1];

// 使用0个物品的价值为0
for (int i = 0; i <= V; i++) {
dp[i] = 0;
}

// 先遍历物品,后遍历重量
for (int i = N - 1; i >= 0; i--) {
for (int v = V; v >= cost[i]; v--) {
int bufang = dp[v];
int fang = dp[v - cost[i]] + value[i];
dp[v] = MAX(bufang, fang);
}
}

for (int j = 0; j <= V; j++) {
printf("%d\t", dp[j]);
}
printf("\n");
printf("%d\n", dp[V]);
}

完全背包

要求物品可以取无限个,但由于包的承重为V,所以每种物品最大数量为 V/cost[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
void CompletePackage_use_n() {

int dp[N][V + 1];

// 0容量的价值为0, 合法
for (int i = 0; i < cost[0]; i++) {
dp[0][i] = 0;
}

// 初始化当包承重大于物品0重量的情况
for (int i = cost[0]; i <= V; i++) {
// 当只装物品0时,包的价值就是物品0的价值
dp[0][i] = i / cost[0] * value[0];
}

// 先遍历物品,后遍历重量
for (int i = 1; i < N; i++) {
for (int v = 0; v <= V; v++) {
dp[i][v] = dp[i - 1][v]; //当重量不够装i时,价值为装i-1的价值,
//此步骤以备i+1时使用(下一个i循环)
for (int k = 1; k <= v / cost[i]; k++) {
dp[i][v] = MAX(dp[i - 1][v], dp[i - 1][v - k * cost[i]] + k * value[i]);
}
}
}

for (int i = 0; i < N; i++) {
for (int j = 0; j <= V; j++) {
printf("%d\t", dp[i][j]);
}
printf("\n");
}
printf("%d\n", dp[N - 1][V]);
}

void CompletePackage_use_n_plus_1() {

int dp[N + 1][V + 1];

// 0容量的价值为0, 合法
for (int i = 0; i <= V; i++) {
dp[0][i] = 0;
}

// 先遍历物品,后遍历重量
for (int i = 1; i <= N; i++) {
for (int v = 0; v <= V; v++) {
dp[i][v] = dp[i - 1][v]; //当重量不够装i时,价值为装i-1的价值,
//此步骤以备i+1时使用(下一个i循环)
for (int k = 1; k <= v / cost[i-1]; k++) {
dp[i][v] = MAX(dp[i - 1][v], dp[i - 1][v - k * cost[i-1]] + k * value[i-1]);
}
}
}

for (int i = 0; i <= N; i++) {
for (int j = 0; j <= V; j++) {
printf("%d\t", dp[i][j]);
}
printf("\n");
}
printf("%d\n", dp[N][V]);
}

void CompletePackage_use_one_array_no_reverse_V() {

int dp[V + 1];

// 0容量的价值为0, 合法
for (int i = 0; i <= V; i++) {
dp[i] = 0;
}

// 先遍历物品,后遍历重量
for (int i = 1; i <= N; i++) {
for (int v = 0; v <= V; v++) {
for (int k = 1; k <= v / cost[i-1]; k++) {
dp[v] = MAX(dp[v], dp[v - k * cost[i-1]] + k * value[i-1]);
}
}
}

for (int j = 0; j <= V; j++) {
printf("%d\t", dp[j]);
}
printf("\n");
printf("%d\n", dp[V]);
}

void CompletePackage_use_one_array_reverse_V() {

int dp[V + 1];

// 0容量的价值为0, 合法
for (int i = 0; i <= V; i++) {
dp[i] = 0;
}

// 先遍历物品,后遍历重量
for (int i = 1; i <= N; i++) {
for (int v = V; v <= cost[i-1]; v--) {
for (int k = 1; k <= v / cost[i-1]; k++) {
dp[v] = MAX(dp[v], dp[v - k * cost[i-1]] + k * value[i-1]);
}
}
}

for (int j = 0; j <= V; j++) {
printf("%d\t", dp[j]);
}
printf("\n");
printf("%d\n", dp[V]);
}

多重背包

多重背包规定了每个物品的最大数量cap[i], 但由于要考虑背包承重,所以真正可以容纳物品的最大个数是max(cap[i], V/cost[i])

疑问

为何不需要将背包排序, 比如按重量排序或按价值排序,再将重量下而价值高的物品优先计算?

即使没有排序,由于第二层循环都是从0->V遍历和放物品i与不放物品i比较,所以顺序不重要

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i < N; i++) {
for (int v = 0; v <= V; v++) {
int bufang = dp[i - 1][v];
dp[i][v] = bufang;
if (v >= cost[i]) {
int fang = dp[i - 1][v - cost[i]] + value[i];
dp[i][v] = MAX(bufang, fang);
}
}
}

算法复杂度和优化

矩阵数组的时间复杂度为O(VN),即两层for循环;空间复杂度为O(VN) 即申请一个矩形数组,经过一元数组优化后,空间复杂度变为O(V)
除此之外,
大多情况下,通过两层遍历,可以只保留重量相同且价值最大的那个物品,这个操作的时间复杂度为O(N^2), 但当最糟糕的情况,即精心设计的物品没有相同重量或者相同价值的情况则此优化无效
另外,先加物品重量大于背包重量的物品忽略,可以加快速度

理解优化

无论是用矩阵数组还是优化成一元数组,最好的理解方式是单步调试一遍

N行与N+1行

两种方式可以通用,只是当N行时,需要提前初始化物品0的情况

初始化问题

我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了 F[0] 为 0,其它F[1..V ] 均设为 −∞,这样就可以保证最终得到的 F[V ] 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 F[0..V ]全部设为 0。

这是为什么呢?可以这样理解:初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,应该被赋值为 -∞ 了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为 0,所以初始时状态的值也就全部为 0了。

贪心算法

由于背包问题里的物品具备重量价值两个维度,所以无法用贪心算法解决。而当维度为1的时候,可以用贪心算法,例如零钱问题和会议安排问题,因为不同零钱价值不同但其“重量”都为1,会议的“重量”也为1
: leetcode上的零钱问题不能用贪心算法

参考

《背包问题九讲》

记一个FakeIt使用问题

FakeIt

FakeIt是一个单元测试工具,类比gmock, 但是比gmock更modern和轻量,因为它支持c++11和header-only

使用方法

FakeIt和gmock都提供Mock和调用计数功能,Mock通常用于接口类,用来定义并实例化接口类对象。gmock和FakeIt都能对调用参数进行校验,但FakeIt的Verify函数还提供在校验失败时打印参数值,这是gmock不具备的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct IAppManager {
// inotify calls when new event
virtual void notify_add_event(EventType event_type,
const std::string& filepath) = 0;
virtual void notify_rename_event(EventType event_type,
const std::string& filepath,
const std::string& filepath_new) = 0;

virtual ~IAppManager() = default;
};

TEST_CASE("Test Inotify") {
Mock<IAppManager> appmanager_mock;
Fake(Dtor(appmanager_mock));
Fake(Method(appmanager_mock, notify_add_event));
Fake(Method(appmanager_mock, notify_rename_event));

auto& app_manager = appmanager_mock.get();
SECTION("test add") {
std::thread t1([&app_manager](){
app_manager.notify_add_event(EventType::File, "filename");
app_manager.notify_add_event(EventType::File, "filename");
app_manager.notify_add_event(EventType::File, "filename");
});
t1.join();
Verify(Method(appmanager_mock, notify_add_event)).Exactly(2);
}
}

这里没有对调用参数校验,而仅对调用次数验证,可以预见,结果失败,因为调用了3次。

问题

上面的测试用例会失败,因为次数不匹配。而这时FakeIt会打印所有调用的参数值,但参数由于是个引用,而且引用在线程退出时被释放,打印一个无效引用导致会抛异常

1
2
due to a fatal error condition:                                                                 
SIGSEGV - Segmentation violation signal

解决办法

对于本测试而言,解决办法就是将传参所引用的对象duration改大,如全局变量或者static,或者在线程外定义它

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TEST_CASE("Test Inotify") {
Mock<IAppManager> appmanager_mock;
Fake(Dtor(appmanager_mock));
Fake(Method(appmanager_mock, notify_add_event));
Fake(Method(appmanager_mock, notify_rename_event));

auto& app_manager = appmanager_mock.get();
SECTION("test add") {
std::string filename = "asd";
std::thread t1([&app_manager, &filename](){
app_manager.notify_add_event(EventType::File, filename);
app_manager.notify_add_event(EventType::File, filename);
app_manager.notify_add_event(EventType::File, filename);
});
t1.join();
Verify(Method(appmanager_mock, notify_add_event)).Exactly(2);
}
}

修改之后,不会触发SIGSEGV异常, 而是能正确打印出调用参数

1
2
3
4
5
6
7
Expected pattern: appmanager_mock.notify_add_event( Any arguments )
Expected matches: exactly 2
Actual matches : 3
Actual sequence : total of 3 actual invocations:
appmanager_mock.notify_add_event(?, asd)
appmanager_mock.notify_add_event(?, asd)
appmanager_mock.notify_add_event(?, asd)

但对于间接调用的接口,且在单元测试里无法控制变量类型,则没有什么办法,只能保证Extractly准确而不用打印参数值

gmock的方式

gmock使用预先设定调用参数,在调用时再判断,所以不会出现无效引用的问题