Chapter 1

请查看左侧菜单来访问更多文章

Emacs的文件管理器

dired1

dired 是 Emacs 自带的文件管理器，操作非常方便，再加上一些扩展之后无疑是一个理想的文件管理器。看看这里来了解如何增强你的 dired 。

Mark & Flag

dired 最方便的一点就是可以对许多文件进行标记，并进行批量操作。标记的方 法有很多，最普通的标记就是 d 为当前文件贴上删除标签，之后可以使用 x 来 真正删除所有贴上删除标签的文件。

dired 还提供了许多预定义的方便的标记操作(当使用 C-u 传递一个前缀参数 时，他们执行相反操作，即去掉标记)，例如：

  • * * 标记所有可执行文件。
  • * @ 标记所有符号链接。
  • * / 标记所有目录(不包括 . 和 .. )。
  • * s 标记所有文件(不高考 . 和 .. )。
  • * . 标记具有给定扩展名的文件。
  • % m REGEXP 或 * % REGEXP 标记所有匹配到给定的正则表达式 的文件。
  • % g REGEXP 标记所有文件 内容 匹配到给定的正则表达式的文件。

另外，还有一些相关的命令：

  • u 去除当前行的标记。
  • <DEL> 上移一行并去除该行的标记。
  • U 去除所有标记。
  • * ? MARKCHAR 或 M-<DEL> 去除所有以 MARKCHAR 标记的文件的标记，如果 传递一个前缀参数，则会对每一个文件要求你确认是否去除标记。
  • t 交换标记，即所有原来标记为 * 的文件被置于未标记状态，原来未标记的 文件被标记为 * ，原来有其他标记的文件不受影响。

上面的操作都是使用 * 进行标记，但是 dired 可以使用更多的字符进行标记， 只是没有提供相应的快捷键操作而已，你可以先以 * 标记，然后使用 * c OLD-MARKCHAR NEW-MARKCHAR 来把 * 标记变换成其他标记，几乎任何字符(当然不包括中文这种多字节的字符)都可以作为标记，不过空格被特殊对待，用于表示所有未标记的文件。

列举了这么多命令，多少有些枯燥，作为一个例子，我们来把当前目录下的所有备份文件移动到 ~/backup 目录下。假设当前目录已经有一些文件被你以 D 标记，但是暂时还不想删除：

  1. 选择个临时标记，比如 t ，只要保证当前 buffer 里面没有已经存在的 这种标记就行了。
  2. * c D t 把当前所有 D 标签换为 t 标签。
  3. ~ 以 D 标记所有备份文件。
  4. * c D * 把 D 标签换为 * 标签。
  5. R ~/backup <RET> 来把所有标记为 * 的文件移动到 ~/backup 目录里面。
  6. * c t D 恢复原来的 D 标记。

当然这要假设你原来没有设定其他的 * 标记，要不然你也可以再添加一个临时标记。总之操作和清晰也很方便，感觉像在汇编语言里面使用寄存器一样，大多数批量操作都是针对 * 标记的，所以对某个标记操作之前需要把他先转换为 * 标记。

另外，还有一个非常强大的标记的方法，绑定到 M-( 或 * ( 上。它可以让你使 用断言来决定标记哪些文件。 C-h f dired-mark-sexp RET 可以得到详细的文档。 这个功能非常强大，有点类似于 find 程序，例如，标记所有没有编译的 Elisp 文件(如果编译了，那么会有一个同名，但是扩展名为 .elc 的文件存在) 的方法 是输入这个断言： (and (string-match "\\.el$" name) (not (file-exists-p (concat name "c")))) 。

文件操作

dired 内建了很多文件操作，对于操作的文件有一个统一的约定，按照顺序是：

  1. 如果你通过 C-u 传递一个前缀参数 N ，那么它对从当前行开始的 N 行执行操作(N也可以是负数)。
  2. 如果有被标记为 * 的文件，则以这些文件为操作对象。
  3. 只对当前光标所在的文件进行操作。

常用操作

这些命令全部绑定到大写字母上，记忆也非常方便：

  • C 拷贝文件。把 dired-recursive-copies 设为非 nil 的值可以递归拷贝目录，通常我们设定为 top ，这表示对于顶层目录 dired 会先进行询问是否要递归拷贝，而其中的子目录则不再询问。如果嫌询问太麻烦，可以直接设置为 always 。
  • D 删除文件。类似的有一个 dired-recursive-deletes 变量可以控制递归删 除。
  • R 重命名文件，也就是移动文件。
  • H 创建硬链接。
  • S 创建软链接。
  • M 修改权限位，即 shell 里面的 chmod 命令。
  • G 修改文件所属的组。
  • O 修改文件的所有者。
  • T 修改文件的修改时间，类似于 shell 命令 touch 。
  • P 打印文件。
  • Z 压缩或解压文件。
  • L 把 Elisp 文件加载进 Emacs 。
  • B 对 Elisp 文件进行 Byte compile 。
  • A 对文件内容进行正则表达式搜索，搜索会在第一个匹配的地方停下，然后 可以使用 M-, 搜索下一个匹配。
  • Q 对文件内容进行交互式的正则表达式替换。

shell 命令

除了这些操作，还可以使用 ! 来执行 shell 命令。这里介绍了自动猜测 shell 命令的办法，就类似于通常的文件管理器里面以关联的程序打开了。

强大的重命名功能

dired 有一个文件名转换的理念，所以转换，并不一定是重命名，还可以是复制和创建链接。所以，除了 % u 和 % l 重命名原文件为大写、小写外，一个使用正则表达式进行转换的命令提供了四个选项： % X 其中 X 可以是 R , C , H 和 S ，分别代表重命名、复制、创建硬链接和创建软链接，他们使用匹配和替换的机制，这有点像 rename 这个程序，例如： % R \.[^.]*$ <RET> .1\& <RET> 给原来的文件名加个标号 1 ，把 foo.txt 变成 foo.1.txt 。

另外，dired 还有一个叫做 Wdired 的扩展可以直接在 dired 的 buffer 里面编辑文件名来达到重命名的效果。使用 M-x wdired-change-to-wdired-mode 进入编辑模式，这个时候可以直接像编辑普通文本一样编辑文件名，还可以添加路径来实现把文件移动到其他目录。除了文件名可以编辑以外，其他部分被标记为只读，但是如果把 wdired-allow-to-change-permissions 设为 t 的话，还可以编辑文件的权限位。编辑完成之后使用 C-c C-c 来应用所做的编辑。非常方便。

排序和过滤

用 C-u s 可以编辑 dired 的 dired-listing-switches 这个变量，从而达到控制排序的方法的目的。 另外 dired 还有一个 k 用于去掉不想显示出来的文件，它并不删除磁盘上的文件，只是临 时从 dired 的 buffer 中去掉他们， g 刷新一下它们又会显示出来，这样，首先用强大的标记功能进行标记，然后使用 k 去掉，就实现了过滤的功能。

子目录操作

dired 允许同时操作当前目录和子目录。在 dired-listing-switches 里面加入 R 选项就可以显示子目录，如果只是想临时显示某个子目录的内容，对该目录执 行 i 操作就会把该子目录的内容添加到 dired 当前 buffer 的末尾并把光标移 动到那里，dired 在移动之前会先设置一个 mark ，所以可以使用 C-u C-<SPC>。

其他功能

还有一些方便的功能，我把几个常用的命令列在这里：

  • + 创建目录
  • w 复制文件名，如果通过 C-u 传递一个前缀参数 0 ，则复制决定路径名， 如果只是 C-u 则复制相对于 dired 当前目录的相对路径。
  • I 把当前文件以 info 文档的格式打开。
  • N 把当前文件以 man 格式打开(使用 WoMan)。
  • Y 为所有标记的文件创建一个到指定目录的相对符号连接(即使用相对路径进 行引用，而不是绝对路径)。

tags: #emacs #dired

堆

堆的简介

堆是优先级队列的实现，是一种数据结构，你可以把它看做一棵完全二叉树。

 index:    1      2      3      4     5     6     7     8     9     10
         +-------------------------------------------------------------+
 array:  | 16  |  14  |  10  |  8  |  7  |  9  |  3  |  2  |  4  |  1  |
         +-------------------------------------------------------------+
                                |
                                |   可以把这个数组想像成二叉树
                                V

 index:    1               array:   16
          / \                       / \
         /   \                     /   \
        2     3                   14    10
       /\     /\                 /\     /\
      /  \   /  \               /  \   /  \
     4   5   6   7             8   7   9   3
    /\   |                    /\   |
   /  \  /                   /  \  /
  8   9 10                  2   4  1

堆的属性

堆结点的访问

通常堆是通过一维数组来实现的，树的根是第一个元素。

在数组起始位置为 1 的情形中（易于理解，如上图）：

  • 父节点 i 的左子节点在位置 (2i)
  • 父节点 i 的右子节点在位置 (2i+1)
  • 子节点 i 的父节点在位置 floor(i/2)

在数组起始位置为 0 的情形中（用于代码中）：

  • 父节点 i 的左子节点在位置 (2i+1)
  • 父节点 i 的右子节点在位置 (2i+2)
  • 子节点 i 的父节点在位置 floor((i-1)/2)

大根堆和小根堆

大根堆 (Max-heap)

  • 大根堆又称最大堆（大顶堆）
  • 最大堆中的最大元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都大于等于其孩子结点（如果存在）

小根堆 (Min-heap)

  • 小根堆又称最小堆（小顶堆）
  • 最小堆中的最小元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都小于等于其孩子结点（如果存在）

堆的操作

堆中定义以下几种操作：

  • 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
  • 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序

我们假设数组起始位置为 1，方便理解。

Max-Heapify

Max-Heapify 是基本操作，我们会一遍又一遍的递归使用它。

例：对堆 A 的根结点（索引为 1 的结点）进行 Max-Heapify 操作Max-Heapify(A, 1)

       (4)
       / \        根结点是 4，它的孩子大于它，所以这个结点要与
      /   \       它的孩子结点中最大的元素 14 进行交换
    (14)   7
    /\     /
   /  \   /
  2   8   1

        14
       / \        交换过后的 4，继续看它的两个孩子是否满足条件
      /   \       发现不满足，这次它和孩子结点中最大的元素 8 进行交换
    (4)    7
    /\     /
   /  \   /
  2  (8)  1

        14
       / \        交换过后的 4 没有孩子，Max-Heapify 操作结束
      /   \
     8    7
    /\    /
   /  \  /
  2   4  1

Build-Max-Heap

Build-Max-Heap(A) 的操作如下 (n 是堆的大小）

for i=n/2 downTo 1:
    do Max-Heapify(A, i)

因为在 n/2 之后的结点是没有子结点的，所以只需要从 n/2 开始一直到 1 执行 Max-Heapify 即可。

Heap-Sort

堆排序的过程是：

  1. 创建一个堆
  2. 把堆首（最大值）和堆尾互换
  3. 把堆的尺寸缩小1
  4. 重复步骤2，直到堆的尺寸为1

Java 代码的实现如下1：

import java.util.Arrays;

public class HeapSort {

    private int[] arr;

    public HeapSort(int[] arr){
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort(){
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1;
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }

        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点 A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。

        if(li > len) return;       // 左子节点索引超出计算范围，直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }

    /**
     * 测试用例
     *
     * 输出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
        new HeapSort(arr).sort();
        System.out.println(Arrays.toString(arr));
    }

}

tags: #数据结构 #排序 #堆

二叉树

简介

如图所示，与堆相比，二叉树要更复杂。堆是一个 数组，我们可以把它简单地可视化为一颗树，而二叉树和堆不同，它实际上是一颗有指针的 树。

本次主要介绍二叉搜索树，二叉搜索树是指一颗空树或者具有下列性质的二叉树：

  • 若任意结点的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
  • 若任意结点的右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
  • 任意结点的左、右子树也分别为二叉搜索树。
  • 没有键值相等的结点。

如下图所示，就是一颗二叉搜索树: 你可以看到根结点30的左子树的值都小于它，右子树的值都大于它

          30
          / \
         /   \
       17     40
       /\
      /  \
     14  20

属性

  • 深度: 对于任意结点n，n的深度为从根到n的唯一路径长，根的深度为0。
  • 高度: 对于任意结点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。

图示如下(高度height，深度depth):

            d0h3
            / \
           /   \
         d1h1  d1h2
         /\      \
        /  \      \
      d2h0 d2h0  d2h1
                   /
                  /
                d3h0

某个结点的高度等于它左右子树高度的最大值+1

操作

这里先声明数的高度为h。 并且在每个元素的结点加入一个表示子树大小的属性（在括号中表示）。

插入

如果我想插入一个元素18到下面的二叉搜索树，并且同时更新子树大小属性，那么流程如下

          30(5)         先将这个元素与根元素比较，18比根元素30小，所以把它插入左子树
          / \               并将元素30的子树大小属性5加上1
         /   \
       17(3)  40(1)    再将这个元素与17比较，18比17大，所以把它插入右子树
       /\                   并将元素17的子树大小属性3加上1
      /  \
   14(1) 20(1)         将这个元素与20比较，18比20小，所以把它插入左子树
                             并将元素20的子树大小属性1加上1，新插入的元素18子树大小为1

从上面的例子可以看出，对其进行插入操作的时间复杂度为O(h)，与树的高度有关。

查找最大与最小值

如果你想找到最小值，只需沿着树的左侧一直找下去，到达叶子结点即为最小值；最大值同理则为沿着右侧一直找下去，根据二叉搜索树的性质不难看出这一点。

对其进行查找最大与最小值操作的时间复杂度为O(h)，与树的高度有关。

查找相邻的较大较小数

对二叉搜索树进行中序遍历即可得到从小到大排序过的序列。

查找小于等于某个数的元素有多少个

  1. 遍历整个树查找你想要查找的元素
  2. 随着查找的路径逐个比较，若小于等于比较元素则加一
  3. 并且累加左子树的子树大小

例如我想查找小于等于40的元素有多少

             30(6)         先将这个元素与30比较，40大于30，(+1)
             / \            然后再累加左子树17的子树大小，(+2)，然后看右子树
            /   \
        17(2)  40(3)    再将这个元素与结点40比较，相等，(+1)
         /      / \       然后再累加左子树38的子树大小，(+1)，查找结束
        /      /   \
    14(1)   38(1) 44(1)

    将上面的数字累加起来，+1+2+1+1，最终得到5，所以小于等于40的元素有5个。

时间复杂度为O(h)，与树的高度有关。

小结

  • 与堆相比，二叉搜索树可以找到相邻的较大较小数，这是堆所不具备的能力。
  • 从上面的操作我们发现时间复杂度与树的高度有关，所以我们要尽量减少树的高度，使之成为平衡树。

平衡树

简介

平衡树是计算机科学中的一类改进的二叉搜索树。一般的二叉搜索树的查询复杂度是根目标结点到树根的距离(即深度)有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。

基本操作

几乎所有平衡树的操作都基于树旋转操作，通过旋转操作可以使得树趋于平衡。对一颗查找树(search tree)进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量n成比例。如果可以让树维持矮矮胖胖的好身材，也就是让h维持在O(log n)左右，完成上述工作就很省时间。能够一直维持好身材，不因新增删除而长歪的搜寻树，叫做平衡树(balanced search tree)。

旋转(Rotate) —— 不破坏左小右大特性的小手术

各种平衡树

  • AVL树
  • 红黑树
  • 加权平衡树(WBT)
  • Treap(Tree+Heap)

这些均可以使查找树的高度为O(log n)

tags: #数据结构 #排序 #二叉搜索树

AVL Tree

简介

在AVL树中，任一结点对应的两颗子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

在开始之前请明确树的高度的概念。

以下面这颗树为例，标明各个结点的高度

          30(2)
          / \
         /   \
       17(1)  40(0)
       /\
      /  \
   14(0) 20(0)

为了方便起见，空结点的高度设定为-1，例如上图右下的40结点，左右孩子都为空，高度看作-1，这样计算像40这样的结点高度时不用指定特殊情况：左右孩子高度最大值加一(-1+1=0)

属性

AVL树每个结点左右子树的高度差不超过1，如上图根结点30，左子树高度为1，右子树高度为0，相差1。

基本操作

旋转(Rotation)

如下图所示，从左到右为对X结点左旋(X结点移动到左侧)，从右到左为对Y结点右旋(Y结点移动到右侧)

           X                                 Y
          / \         left_rotate(X)        / \
         /   \        ---------------->    /   \
       A子树  Y    <----------------      X   C子树
              /\      right_rotate(Y)    /\
             /  \                       /  \
          B子树 C子树               A子树 B子树

此操作花费恒定的O(1)时间，而且变换后满足二叉搜索树的属性，你可以看到操作前后它的中序遍历都是A,X,B,Y,C

插入

  1. 插入到二叉搜索树
  2. 修复AVL属性

第一步就是很普通的把结点插入到二叉搜索树，重点在第二步如何保持AVL树的属性，请看下面的两种情况(括号内为结点高度)：

如果X的右子树(Y树)右侧偏重(C子树高度大于B子树高度)，进行左旋X操作

           X(k)                            Y(k-1)
          / \         left_rotate(X)        / \
         /   \        ---------------->    /   \
   A子树(k-3) Y(k-1)                   X(k-2)  C子树(k-2)
              /\                         /\
             /  \                       /  \
     B子树(k-3) C子树(k-2)      A子树(k-3) B子树(k-3)
     
否则，对Z进行右旋操作，再对X进行左旋操作

           X          right_totate(Z)        Y
          / \          left_rotate(X)       / \
         /   \        ---------------->    /   \
      A子树   Z                           X     Z
              /\                         /\     /\
             /  \                       /  \   /  \
            Y   D子树                  A   B   C   D
           /\                         子  子   子  子
          /  \                        树  树   树  树
      B子树  C子树

你可以使用它进行排序，逐个插入结点时间复杂度为O(nlogn)，之后进行中序遍历时间复杂度为O(n)，就可以得到递增的序列。

tags: #数据结构 #排序 #二叉搜索树 #AVL树

FFmpeg转码常用操作

简介1

FFmpeg 是一个自由软件，可以运行音频和视频多种格式的录影、转换、流功能，包含了libavcodec——这是一个用于多个项目中音频和视频的解码器库，以及libavformat——一个音频与视频格式转换库。 “FFmpeg”这个单词中的“FF”指的是“Fast Forward”。

自动化工具

下面是一个用来生成参数的在线工具: FFmpeg Commander

基本转换2

FFmpeg的默认设置相当聪明，通常它会自动选择正确的编解码器和容器而无需任何复杂的配置。

例如，假设您有一个MP3文件并希望将其转换为OGG文件:

ffmpeg -i input.mp3 output.ogg

此命令采用名为input.mp3的MP3文件，并将其转换为名为output.ogg的OGG文件。从FFmpeg的角度来看，这意味着将MP3音频流转换为Vorbis音频流并将此流包装到OGG容器中。您不必指定流或容器类型，因为FFmpeg为您找到了它。

这也适用于视频:

ffmpeg -i input.mp4 output.webm

由于WebM是一种定义良好的格式，FFmpeg会自动知道它可以支持哪些视频和音频，并将流转换为有效的WebM文件。

根据您选择的容器，这并不总是有效。例如，像Matroska这样的容器可以处理几乎任何你想要放入的流，无论它们是否有效。这意味着命令:

ffmpeg -i input.mp4 output.mkv

可能会导致文件具有与input.mp4相同的编解码器，这可能是您想要的，也可能不是。

选择你的编解码器

那么当你想使用像Matroska这样的容器(几乎可以处理任何流)但仍想修改输出的编码时，您可以使用-c标志选择所需的编解码器。 此标志允许您设置用于每个流的不同编解码器。 例如，要将音频流设置为Vorbis，您将使用以下命令:

ffmpeg -i input.mp3 -c:a libvorbis output.ogg

更改视频和音频流也可以这样做:

ffmpeg -i input.mp4 -c:v vp9 -c:a libvorbis output.mkv

这将使Matroska容器具有VP9视频流和Vorbis音频流，与我们之前制作的WebM基本相同。

命令ffmpeg -codecs将打印FFmpeg知道的每个编解码器。 此命令的输出将根据您安装的FFmpeg的版本而更改。

使用-target参数匹配行业标准，参数值可以是vcd、svcd、dvd、dv、dv50等，可能还需要加上电视制式作为前缀（pal-、ntsc-或film-）。如下:

ffmpeg -i input.mp3 -target pal-dvd output.ogg

更改单个流

通常情况下，您的文件部分正确，只有一个错误格式的流。 重新编码正确的流可能非常耗时。FFmpeg可以帮助解决这种情况:

ffmpeg -i input.webm -c:v copy -c:a flac output.mkv

此命令将视频流从input.webm复制到output.mkv ，并将Vorbis音频流编码为FLAC。

更换容器

前面的示例可以应用于音频和视频流，允许您从一种容器格式转换为另一种容器格式，而无需进行任何其他流编码:

ffmpeg -i input.webm -c:av copy output.mkv

影响质量

现在我们已经掌握了编解码器，接下来的问题是:我们如何设置每个流的质量？

最简单的方法是改变比特率，这可能会或可能不会导致不同的质量。人类的视听能力并不像我们想的那样清晰明确。有时候改变比特率会对主观质量产生巨大影响。其他时候它可能只会改变文件大小。有时候如果不试一试就很难说出会发生什么。

要设置每个流的比特率，请使用-b标志，它以与-c标志类似的方式工作，除了您设置比特率的编解码器选项。

例如，要更改视频的比特率，您可以像这样使用它:

ffmpeg -i input.webm -c:a copy -c:v vp9 -b:v 1M output.mkv

这将从input.webm复制音频(-c:a copy)，并将视频转换为比特率为1M/s(-b:v)的VP9编解码器(-c:v vp9)，所有这些都捆绑在一起一个Matroska容器(output.mkv)。

我们可以影响质量的另一种方法是使用-r选项调整视频的帧速率:

ffmpeg -i input.webm -c:a copy -c:v vp9 -r 30 output.mkv

这创建了一个新的Matroska，其中复制了音频流，并且视频流的帧速率被强制为每秒30帧，而不是使用来自输入的帧速率(-r 30)。

您还可以使用FFmpeg调整视频的尺寸。 最简单的方法是使用预定的视频大小:

ffmpeg -i input.mkv -c:a copy -s hd720 output.mkv

这会在输出中将视频修改为1280x720，但如果需要，您可以手动设置宽度和高度:

ffmpeg -i input.mkv -c:a copy -s 1280x720 output.mkv

这将生成与上一条命令完全相同的输出。如果要在FFmpeg中设置自定义尺寸，请记住宽度参数(1280)在高度(720)之前。

调整帧速率和比特率是影响媒体质量的两种原始但有效的技术。 如果现有源的质量已经很低，则将这些值设置得非常高，无法提高现有源的质量。

更改这些设置对于快速减少高质量流以缩小文件大小非常有效。调整视频大小无法提高质量，但可以使其更适合平板电脑而非电视。将640x480视频的大小更改为4K不会改善它。

改变文件的质量是一个非常主观的问题，这意味着没有一种方法可以每次都有效。最好的方法是做一些小修改，并测试它是否看起来或听起来更合适。

修改流

ffmpeg -i input.mkv -c:av copy -ss 00:01:00 -t 10 output.mkv

这将复制视频和音频流(-c:av copy)，并且修剪视频。 -t选项将剪切持续时间设置为10秒， -ss选项设置视频的开始点以进行剪裁，在本例中为一分钟(00:01:00)。 您可以更精确，而不仅仅是小时，分钟和秒，如果需要，可以缩短到几毫秒。

旋转视频3

想让视频顺时针旋转90度。这时候，可以使用-vf参数加入一个过滤器:

ffmpeg -i input.mp3 -vf "rotate=90*PI/180" output.ogg

叠加图片

如果我们希望在一段视频上叠加一张图片。可以简单实现如下:

ffmpeg -i input.mp3 -i image.png -filter_complex 'overlay' output.ogg

提取音频

有时你并不想要图像，你只需要音频。 幸运的是，在FFmpeg中使用-vn标志非常简单:

ffmpeg -i input.mkv -vn audio_only.ogg

此命令仅从输入中提取音频，将其编码为Vorbis，并将其保存到audio_only.ogg中 。 现在你有一个独立的音频流。 您也可以使用-an和-sn标志以相同的方式去除音频和字幕流。

制作GIF

使用-an标志，类似于我们上面所做的，比创建动画GIF要好，如果你想制作一个没有音频的视频，但有很多地方支持不支持不同视频格式的GIF。

ffmpeg -i input.mkv output.gif

此命令创建与输入文件具有相同尺寸的GIF。这通常不是一个好主意，因为相对于其他视频格式，GIF不能很好地压缩(根据我的经验，GIF将比源视频大8倍)。 使用-s选项将GIF的大小调整为稍微小一些可能会有所帮助，尤其是在输入源非常大的情况下，例如高清视频。

获取视频信息

有时您需要知道的是媒体文件内部信息，有几种工具可以做到这一点，最简单的是ffprobe工具:

ffprobe -i input.mp4

比较强大的工具有MediaInfo，运行命令mediainfo inputFile.mkv以人类可读的形式输出有关输入文件的信息列表。

更多

FFmpeg还有更多更强大的用法，具体请参阅文档。

如果您使用的是带有图形界面的工具来转换多媒体，那么Handbrake在Linux，Mac OS X和Windows上都是非常好用的。

tags: #ffmpeg #转码

VIM快捷键

基本移动

keydescription
h l k j左,右一字符;上一行,下一行
b w左,右到一个词或记号
ge e左,右到词或记号的末尾
{ }上,下一段的开始
( )上,下一句的开始
0 gm一行的开始,中间
^ $一行的第一,最后一个字符
nG ngg第n行,默认为最后一行,第一行
n%文件的n%(n必须指定)
n|当前行的第n列
%匹配的括号,注释,#define
nH nL从窗口的开始,末尾算起的第n行
M窗口的中间一行

插入 替换

keydescription
i a在光标前,后插入
I A在行首,行尾插入
gI在第一列插入
o O在当前行下面,上面插入新行
rc用c替换光标下的字符
grc同r,但不影响布局
R从光标处开始替换多个字符
gR同R,但不影响布局
cm更改到移动命令m处的文本
cc or S更改当前行
C更改到行尾
s更改一个字符并插入
~切换大小写并推进光标
g~m切换大小写到移动命令m处的文本
gum gUm小写化,大写化到移动命令m处的文本
<m >m向左,右缩进到移动命令m处的文本
n<< n>>向左,右缩进n列

删除

keydescription
x X删除光标下,光标前的字符
dm删除到移动命令m处
dd D删除当前行,删除到行末
J gJ当前行与下一行合并,不包括空格
:rd删除r行
:rdx删除r行并存入寄存器x

插入模式

keydescription
^Vc ^Vn按照字面意思插入c,插入十进制字符n
^A插入上次插入过的文本
^@同^A并且停止插入进入命令模式
^Rx ^R^Rx插入寄存器x的内容,字面意思
^N ^P在光标前,后文本补全
^W删除光标前的词
^U删除所有当前行插入的字符
^D ^T向左,右缩进一个单位长度
^Kc1c2 or c1←c2输入复合字母**\c1,c2**
^Oc临时在命令模式运行命令c
^X^E ^X^Y向上,下滚动
or ^[取消编辑进入编辑模式

复制

keydescription
"x对下个删除,复制,粘贴操作指定寄存器x
:reg显示所有寄存器的内容
:reg x显示寄存器x的内容
ym复制到移动命令m处
yy or Y复制当前行到寄存器
p P在光标之后,之前粘贴寄存器内容
]p [p同p,P并自动缩进
gp gP同p,P并把光标置于新文本后

高级插入

keydescription
g?m到移动命令m处执行rot13编码
n^A n^X光标处数字**+n,-n**
gqm格式化到移动命令m的行来修复宽度
:rce w从范围r到宽度w的中间行
:rle i范围r缩进i的左对齐的行
:rri w范围r到宽度w的右对齐的行
!mc通过命令c过滤到移动命令m处
n!!c通过命令c过滤n行
:r!c通过命令c过滤范围r行

tags: #vim

免Root修改Android应用的Shared Preferences

准备工作

  1. 一台启用调试模式的Android手机,无需root
  2. 一台电脑(本文使用Linux操作系统)
  3. 必备软件(如:adb openssl tar dd star等)

前言

本文以破解游戏元气骑士为例进行演示，破解思路来源于此处

具体步骤

  1. 本文所述教程是在Linux平台进行的,请保证你的电脑有tar, dd, openssl, star组件,其中star从此处下载

  2. 首先需要通过adb以备份的形式将元气骑士存档数据导出,命令如下:

    adb backup com.ChillyRoom.DungeonShooter -f backup.ab

    需要在手机上授权备份操作,其中com.ChillyRoom.DungeonShooter是元气骑士的包名,backup.ab是导出的存档的文件名

  3. 上一步导出的.ab文件是Android备份文件,其中前24字节是文件头,我们需要用dd把前24字节剔除,这样剩下的就是压缩后的tar归档文件,再使用openssl进行解压,可以通过以下命令完成:

    dd if=backup.ab bs=24 skip=1 | openssl zlib -d > backup.tar

  4. 现在我们得到了一个打包后的存档文件,现在需要用tar把所有文件的打包顺序记录下来,修改数据之后的打包流程需要用到,使用如下命令:

    tar -tf backup.tar > backup.list

    保存的list文件名为backup.list

  5. 现在就可以将tar文件解压了

    tar -xf backup.tar

    解压完成之后会有一个app目录,下一级是游戏的包名命名的目录,再往下就是分类的所有存档数据,如下所示(一些本次教程用不到的文件被隐藏):

apps
    └── com.ChillyRoom.DungeonShooter
        ├── db
        ├── ef
        ├── f
        ├── r
        └── sp-------->表示Shared Preferences
            ├── admob.xml
            ├── appsflyer-data.xml
            ├── avidly_ads_analysis_key_dic_.xml
            ├── avidly_ads_sdk.xml
            ├── cbPrefs.xml
            ├── com.ChillyRoom.DungeonShooter_preferences.xml
            ├── com.ChillyRoom.DungeonShooter.v2.playerprefs.xml -->此文件是需要修改的文件
            ├── com.facebook.ads.FEATURE_CONFIG.xml
            ├── com.facebook.internal.preferences.APP_SETTINGS.xml
            ├── com.facebook.sdk.appEventPreferences.xml
            ├── com.facebook.sdk.attributionTracking.xml
            ├── com.google.android.gms.analytics.prefs.xml
            ├── com.google.android.gms.appid.xml
            ├── com.google.android.gms.measurement.prefs.xml
            ├── com.google.android.gms.signin.xml
            ├── com.vungle.sdk.xml
            ├── DEBUG_PREF.xml
            ├── FBAdPrefs.xml
            ├── ktplay.xml
            ├── SDKIDFA.xml
            └── WebViewChromiumPrefs.xml
  1. 如上所示,我们打开com.ChillyRoom.DungeonShooter.v2.playerprefs.xml文件,根据各个变量的名字我们可以看出一些含意:
    <string name="c13_unlock">false</string> 
    变量名中的c为character角色的缩写,这个变量的意义是13号角色是否解锁,这样我们可以通过把指改为true来达到解锁角色的目的

    <int name="c12_skin3" value="-1" /> 
    同理,此处应该为12号角色的3号皮肤,对于值的分析我个人认为如果是2000这样的数值应该为需要花费宝石解锁,为0时是需要花费现金解锁,为-1时是尚未推出的皮肤,为1则为已解锁.这里请自行修改
    
    <int name="last_gems" value="2123" />
    <int name="gems" value="2441" /> 
    这里两个变量是宝石数量,可以自行修改想要的数值
    
    其他数据以及其他配置文件的数据请自行发挥,本文不作分析

  1. 在上一步修改完数据后接下来要做的就是将修改完成的数据导回去,需要用到star工具,下载链接上面已经提到过,命令如下:

    star -c -v -f newbackup.tar -no-dirslash list=backup.list

    用到了之前导出的列表文件,打包的新文件名为newbackup.tar

  2. 现在需要用dd把之前剔除的Android备份文件的文件头取出来,使用如下命令:

    dd if=backup.ab bs=24 count=1 of=newbackup.ab

    把原备份文件backup.ab的文件头保存为newbackup.ab

  3. 再把修改过的存档文件压缩,前面拼上文件头:

    openssl zlib -in newbackup.tar >> newbackup.ab

  4. 大功告成,新的备份文件打包完成,最后一步,把修改过的备份文件newbackup.ab通过adb恢复回去:

    adb restore newbackup.ab

  5. 这个时候就可以打开你的游戏查看修改的成果啦!Happy Hacking!

tags: #Android

Relaying UDP broadcasts

文章类型为转载1

iptables -t mangle -A INPUT -i eth0 -d 255.255.255.255 -j TEE --gateway 10.1.1.255

The above iptables rule copies broadcast traffic received on the eth0 network interface to another network interface (the one whose broadcast address is 10.1.1.255). Note that this is one-way only. We can't add a second rule for the other direction without creating an infinite packet loop. We need to play tricks with the TTL for that!

Incoming broadcast packets typically have a TTL of 64 or 128. TEE uses the kernel function nf_dup_ipv4() to copy the packet, which already decrements the TTL if the rule is in INPUT or PREROUTING. Note that a packet with TTL=0 will still be accepted by the destination, but will no longer be routed. But TEE itself does not check for TTL=0 and happily copies such packets. So we need to prevent that too, since what we do is effectively routing.

The improved rule adds TTL sanity check:

iptables -t mangle -A INPUT -i eth0 -d 255.255.255.255 -m ttl --ttl-gt 0 -j TEE --gateway 10.1.1.255

If we want to add a rule for the other direction as well...

iptables -t mangle -A INPUT -i eth1 -d 255.255.255.255 -m ttl --ttl-gt 0 -j TEE --gateway 10.1.0.255

then we easily create a packet loop, since the copy of a packet on eth0 will now also match the rule on eth1. To prevent that we need to ensure that the copied packet has TTL=0. We can do that by simply setting the TTL=1 of all incoming broadcasts before passing them to TEE. Then no more loops should occur. The complete rule set for merging a broadcast domain across networks is then:

iptables -t mangle -A INPUT -i eth0 -d 255.255.255.255 -m ttl --ttl-gt 0 -j TTL --ttl-set 1
iptables -t mangle -A INPUT -i eth1 -d 255.255.255.255 -m ttl --ttl-gt 0 -j TTL --ttl-set 1
iptables -t mangle -A INPUT -i eth0 -d 255.255.255.255 -m ttl --ttl-gt 0 -j TEE --gateway 10.1.1.255
iptables -t mangle -A INPUT -i eth1 -d 255.255.255.255 -m ttl --ttl-gt 0 -j TEE --gateway 10.1.0.255

Make sure to monitor your broadcast traffic to detect any misconfiguration after that change:

tcpdump -vnpi eth0 ip broadcast

tags: #Linux #UDP

Kali Linux升级时PG数据库相关问题

GVM升级问题

升级Kali Linux系统后, GVM扫描器无法启动, 运行gvm-check-setup后提示PostgreSQL版本有问题, 如下所示:

gvm-check-setup 22.4.0
  Test completeness and readiness of GVM-22.4.0
Step 1: Checking OpenVAS (Scanner)... 
        OK: OpenVAS Scanner is present in version 22.4.0.
        OK: Notus Scanner is present in version 22.4.1.
        OK: Server CA Certificate is present as /var/lib/gvm/CA/servercert.pem.
Checking permissions of /var/lib/openvas/gnupg/*
        OK: _gvm owns all files in /var/lib/openvas/gnupg
        OK: redis-server is present.
        OK: scanner (db_address setting) is configured properly using the redis-server socket: /var/run/redis-openvas/redis-server.sock
        OK: redis-server is running and listening on socket: /var/run/redis-openvas/redis-server.sock.
        OK: redis-server configuration is OK and redis-server is running.
        OK: the mqtt_server_uri is defined in /etc/openvas/openvas.conf
        OK: _gvm owns all files in /var/lib/openvas/plugins
        OK: NVT collection in /var/lib/openvas/plugins contains 83468 NVTs.
        OK: The notus directory /var/lib/notus/products contains 377 NVTs.
Checking that the obsolete redis database has been removed
        OK: No old Redis DB
        OK: ospd-OpenVAS is present in version 22.4.0.
Step 2: Checking GVMD Manager ... 
        OK: GVM Manager (gvmd) is present in version 22.4.0~dev1.
Step 3: Checking Certificates ... 
        OK: GVM client certificate is valid and present as /var/lib/gvm/CA/clientcert.pem.
        OK: Your GVM certificate infrastructure passed validation.
Step 4: Checking data ... 
        OK: SCAP data found in /var/lib/gvm/scap-data.
        OK: CERT data found in /var/lib/gvm/cert-data.
Step 5: Checking Postgresql DB and user ... 
        ERROR: The default postgresql version is not the one used for gvmd compilation: (14, need 15).
        FIX: Please use pg_upgradecluster to upgrade your postgresql installation

 ERROR: Your GVM-22.4.0 installation is not yet complete!
 
Please follow the instructions marked with FIX above and run this
script again.

首先停止PostgreSQL服务

sudo systemctl stop postgresql

然后根据系统升级前后的PostgreSQL版本, 例如之前为14, 升级后为15, 并且确保没有任何有用的数据存储在15版本上, 执行如下命令删除15版本的cluster(注意!会删除15版本的数据!)

sudo pg_dropcluster --stop 15 main

然后使用以下命令进行迁移

sudo pg_upgradecluster 14 main

之后根据gvm-check-setup推荐的步骤继续进行即可

登录相关

使用如下命令查看账户

sudo runuser -u _gvm -- gvmd --get-users

如果您看到您的帐户但无法登录，您可以运行此命令来重置密码

sudo runuser -u _gvm -- gvmd --user=admin --new-password=NEWPASSWORD

如果重置密码后无法登录，可以尝试运行以下命令重启gvm服务

sudo systemctl restart gvmd

您还可以创建一个新的 GVM 用户，运行以下命令

sudo runuser -u _gvm -- gvmd --create-user=USER --new-password=NEWPASSWORD

要删除 GVM 用户，可以运行以下命令

sudo runuser -u _gvm -- gvmd --delete-user=USER

Metasploit升级问题

DETAIL:  The database was created using collation version 2.36, but the operating system provides version 2.37.

HINT:  Rebuild all objects in this database that use the default collation and run ALTER DATABASE msf REFRESH COLLATION VERSION, or build PostgreSQL with the right library version.

修复方式:

sudo -u postgres psql -U postgres -d msf

REINDEX DATABASE msf;

ALTER DATABASE msf REFRESH COLLATION VERSION;

tags: #Kali #PostgreSQL

SSL加密算法配置

相关资料

RFC文档中有推荐的和不应使用的加密算法(第4节) RFC 9142 Key Exchange (KEX) Method Updates and Recommendations for Secure Shell (SSH)

SSL配置文件生成器, 可以根据安全级别和应用软件版本生成对应的配置文件 SSL Configuration Generator SSL Config Generator

外部扫描

可以使用nmap script

nmap -p22 <ip> -sC # Send default nmap scripts for SSH
nmap -p22 <ip> -sV # Retrieve version
nmap -p22 <ip> --script ssh2-enum-algos # Retrieve supported algorythms 
nmap -p22 <ip> --script ssh-hostkey --script-args ssh_hostkey=full # Retrieve weak keys
nmap -p22 <ip> --script ssh-auth-methods --script-args="ssh.user=root" # Check authentication methods

或者metasploit

msf> use scanner/ssh/ssh_enumusers

tags: #SSL

XPath提取元素

查询

使用xmllint或者XMLStarlet工具可以在terminal对html/xml文件进行操作, xmllint需要--html参数启用html解析器, 以下则以XMLStarlet为例进行说明: 由于在我的系统上xmlstarlet程序有名为xml的符号链接, 所以下文以xml代替

xml fo -H -R input.html 2>/dev/null | xml sel -t -v '//*[@class="odd"]' -c '(//*[text()="IP"])[1]/../following-sibling::td' -n

首先需要使用fo(format)子命令加上-H(HTML格式解析)与-R(尝试进行文件修复)对html文档进行处理, 并忽略所有警告信息 之后使用普通的sel(select)对元素进行查询

下面提供XPath的语法文档和XMLStarlet的官方文档链接: XMLStarlet Command Line XML Toolkit XPath Docs

tags: #XPath