/* This file is part of apfs-fuse, a read-only implementation of APFS (Apple File System) for FUSE. Copyright (C) 2017 Simon Gander Apfs-fuse is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version. Apfs-fuse is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with apfs-fuse. If not, see . */ #include "Unicode.h" #include #include #include #include #include #if defined(__linux__) || defined(__APPLE__) #include #endif #include #include "Util.h" #include "Crc32.h" #include #include extern "C" { #include #include } static Crc32 g_crc(true, 0x1EDC6F41); uint64_t Fletcher64(const uint32_t *data, size_t cnt, uint64_t init) { size_t k; uint64_t sum1 = init & 0xFFFFFFFFU; uint64_t sum2 = (init >> 32); for (k = 0; k < cnt; k++) { sum1 = (sum1 + data[k]); sum2 = (sum2 + sum1); } sum1 = sum1 % 0xFFFFFFFF; sum2 = sum2 % 0xFFFFFFFF; return (static_cast(sum2) << 32) | static_cast(sum1); } bool VerifyBlock(const void *block, size_t size) { uint64_t cs; const uint32_t * const data = reinterpret_cast(block); size /= sizeof(uint32_t); cs = *reinterpret_cast(block); if (cs == 0) return false; if (cs == 0xFFFFFFFFFFFFFFFFULL) return false; cs = Fletcher64(data + 2, size - 2, 0); cs = Fletcher64(data, 2, cs); return cs == 0; } bool IsZero(const uint8_t* data, size_t size) { for (size_t k = 0; k < size; k++) { if (data[k] != 0) return false; } return true; } bool IsEmptyBlock(const void *data, size_t blksize) { blksize /= sizeof(uint64_t); const uint64_t *qdata = reinterpret_cast(data); for (size_t k = 0; k < blksize; k++) { if (qdata[k] != 0) return false; } return true; } void DumpHex(std::ostream &os, const uint8_t *data, size_t size, size_t lineSize) { using namespace std; size_t i, j; uint8_t b; if (size == 0) return; os << hex << uppercase << setfill('0'); for (i = 0; i < size; i += lineSize) { os << setw(4) << i << ": "; for (j = 0; (j < lineSize) && ((i + j) < size); j++) os << setw(2) << static_cast(data[i + j]) << ' '; for (; j < lineSize; j++) os << " "; os << "- "; for (j = 0; (j < lineSize) && ((i + j) < size); j++) { b = data[i + j]; if (b >= 0x20 && b < 0x7F) os << b; else os << '.'; } os << endl; } // os << dec; } // Like DumpHex, but prints a label. void DumpBuffer(const uint8_t *data, size_t len, const char *label) { std::cout << "dumping " << label << std::endl; DumpHex(std::cout, data, len); } std::string uuidstr(const apfs_uuid_t &uuid) { using namespace std; stringstream st; int k; st << hex << uppercase << setfill('0'); for (k = 0; k < 4; k++) st << setw(2) << static_cast(uuid[k]); st << '-'; for (k = 4; k < 6; k++) st << setw(2) << static_cast(uuid[k]); st << '-'; for (k = 6; k < 8; k++) st << setw(2) << static_cast(uuid[k]); st << '-'; for (k = 8; k < 10; k++) st << setw(2) << static_cast(uuid[k]); st << '-'; for (k = 10; k < 16; k++) st << setw(2) << static_cast(uuid[k]); return st.str(); } std::string hexstr(const uint8_t *data, size_t size) { using namespace std; std::ostringstream st; size_t k; st << hex << uppercase << setfill('0'); for (k = 0; k < size; k++) st << setw(2) << static_cast(data[k]); return st.str(); } void dump_utf8(std::ostream &st, const uint8_t* str) { size_t ptr = 0; uint8_t ch; char32_t uch; int cnt; st << std::hex << std::uppercase; while (str[ptr] != 0) { ch = str[ptr++]; if (ch < 0x80) { uch = ch; cnt = 0; } else if (ch < 0xC0) { break; } else if (ch < 0xE0) { uch = ch & 0x1F; cnt = 1; } else if (ch < 0xF0) { uch = ch & 0x0F; cnt = 2; } else if (ch < 0xF8) { uch = ch & 0x07; cnt = 3; } else break; for (; cnt > 0; --cnt) { ch = str[ptr++]; if ((ch & 0xC0) == 0x80) uch = (uch << 6) | (ch & 0x3F); else break; } st << uch << ' '; } st << str << std::endl; } void dump_utf32(std::ostream &st, const char32_t *str, size_t size) { size_t k; st << std::hex << std::uppercase; for (k = 0; k < size; k++) st << str[k] << ' '; for (k = 0; k < size; k++) if (str[k] >= 0x20 && str[k] < 0x7F) st << static_cast(str[k]); else st << '.'; st << std::endl; } uint32_t HashFilename(const uint8_t* utf8str, uint16_t name_len, bool case_fold) { std::vector utf32; std::vector utf32_nfd; uint32_t hash; Utf8toUtf32(utf32, utf8str); NormalizeFoldString(utf32_nfd, utf32, case_fold); #if 0 if (g_debug & Dbg_Dir) { dump_utf32(utf32.data(), utf32.size()); dump_utf32(utf32_nfd.data(), utf32_nfd.size()); } #endif g_crc.SetCRC(0xFFFFFFFF); g_crc.Calc(reinterpret_cast(utf32_nfd.data()), utf32_nfd.size() * sizeof(char32_t)); hash = g_crc.GetCRC(); hash = ((hash & 0x3FFFFF) << 10) | (name_len & 0x3FF); return hash; } int apfs_strncmp(const uint8_t *s1, size_t s1_len, const uint8_t *s2, size_t s2_len) { while (s1_len > 0 && s2_len > 0) { if (*s1 < *s2) return -1; if (*s1 > *s2) return 1; if (*s1 == 0) return 0; ++s1; ++s2; --s1_len; --s2_len; } if (s2_len) return -1; if (s1_len) return 1; return 0; } int StrCmpUtf8NormalizedFolded(const uint8_t* s1, const uint8_t* s2, bool case_fold) { std::vector s1_u32; std::vector s2_u32; std::vector s1_u32_nfd; std::vector s2_u32_nfd; size_t k; Utf8toUtf32(s1_u32, s1); Utf8toUtf32(s2_u32, s2); NormalizeFoldString(s1_u32_nfd, s1_u32, case_fold); NormalizeFoldString(s2_u32_nfd, s2_u32, case_fold); s1_u32_nfd.push_back(0); s2_u32_nfd.push_back(0); k = 0; while (true) { if (s1_u32_nfd[k] < s2_u32_nfd[k]) return -1; if (s1_u32_nfd[k] > s2_u32_nfd[k]) return 1; if (s1_u32_nfd[k] == 0 || s2_u32_nfd[k] == 0) break; ++k; } return 0; } bool Utf8toUtf32(std::vector &str32, const uint8_t* str) { size_t ip = 0; int cnt = 0; char32_t ch; uint8_t c; bool ok = true; while (str[ip] != 0) { c = str[ip++]; if (c < 0x80) { ch = c; cnt = 0; } else if (c < 0xC0) { ok = false; break; } else if (c < 0xE0) { ch = c & 0x1F; cnt = 1; } else if (c < 0xF0) { ch = c & 0x0F; cnt = 2; } else if (c < 0xF8) { ch = c & 0x07; cnt = 3; } else { ok = false; break; } for (; cnt > 0; --cnt) { c = str[ip++]; if ((c & 0xC0) == 0x80) ch = (ch << 6) | (c & 0x3F); else { ok = false; break; } } if (!ok) break; str32.push_back(ch); if (ch == 0) break; } return ok; } bool GetPassword(std::string &pw) { #if defined(__linux__) || defined(__APPLE__) struct termios told, tnew; FILE *stream = stdin; /* Turn echoing off and fail if we can’t. */ if (tcgetattr (fileno (stream), &told) != 0) return false; tnew = told; tnew.c_lflag &= ~ECHO; if (tcsetattr (fileno (stream), TCSAFLUSH, &tnew) != 0) return false; /* Read the password. */ std::getline(std::cin, pw); /* Restore terminal. */ (void) tcsetattr (fileno (stream), TCSAFLUSH, &told); std::cout << std::endl; return true; #else std::getline(std::cin, pw); std::cout << std::endl; return true; #endif } size_t DecompressZLib(uint8_t *dst, size_t dst_size, const uint8_t *src, size_t src_size) { // size_t nwr = 0; int ret; z_stream strm; memset(&strm, 0, sizeof(strm)); strm.zalloc = Z_NULL; strm.zfree = Z_NULL; strm.avail_in = src_size; strm.avail_out = dst_size; strm.next_in = const_cast(src); strm.next_out = dst; ret = inflateInit2(&strm, 15); if (ret != Z_OK) { std::cerr << "DecompressZLib: inflateInit failed." << std::endl; return 0; } do { ret = inflate(&strm, Z_NO_FLUSH); if (ret == Z_NEED_DICT || ret == Z_DATA_ERROR || ret == Z_MEM_ERROR) { strm.avail_out = 0; break; } } while (ret != Z_STREAM_END); inflateEnd(&strm); return dst_size - strm.avail_out; } size_t DecompressADC(uint8_t * dst, size_t dst_size, const uint8_t * src, size_t src_size) { size_t in_idx = 0; size_t out_idx = 0; uint8_t ctl; int len; int dist; int cnt; for (;;) { if (in_idx >= src_size) break; if (out_idx >= dst_size) break; ctl = src[in_idx++]; if (ctl & 0x80) { len = (ctl & 0x7F) + 1; for (cnt = 0; cnt < len; cnt++) dst[out_idx++] = src[in_idx++]; } else { if (ctl & 0x40) { len = ctl - 0x3C; dist = src[in_idx++]; dist = (dist << 8) | src[in_idx++]; dist += 1; } else { len = ((ctl >> 2) & 0xF) + 3; dist = (((ctl & 3) << 8) | src[in_idx++]) + 1; } for (cnt = 0; cnt < len; cnt++) { dst[out_idx] = dst[out_idx - dist]; out_idx++; } } } assert(in_idx == src_size); assert(out_idx == dst_size); return out_idx; } size_t DecompressLZVN(uint8_t * dst, size_t dst_size, const uint8_t * src, size_t src_size) { lzvn_decoder_state state; memset(&state, 0, sizeof(state)); state.src = src; state.src_end = src + src_size; state.dst = dst; state.dst_begin = dst; state.dst_end = dst + dst_size; state.dst_current = dst; lzvn_decode(&state); return static_cast(state.dst - dst); } size_t DecompressBZ2(uint8_t * dst, size_t dst_size, const uint8_t * src, size_t src_size) { bz_stream strm; memset(&strm, 0, sizeof(strm)); BZ2_bzDecompressInit(&strm, 0, 0); strm.next_in = const_cast(reinterpret_cast(src)); strm.avail_in = src_size; strm.next_out = reinterpret_cast(dst); strm.avail_out = dst_size; BZ2_bzDecompress(&strm); BZ2_bzDecompressEnd(&strm); return strm.total_out_lo32; } size_t DecompressLZFSE(uint8_t * dst, size_t dst_size, const uint8_t * src, size_t src_size) { return lzfse_decode_buffer(dst, dst_size, src, src_size, nullptr); } size_t DecompressLZBITMAP(uint8_t* dst, size_t dst_size, const uint8_t* src, size_t src_size) { uint8_t scratch[0x2000]; uint8_t flags; uint32_t compressed_size; uint32_t uncompressed_size; uint32_t distances_offset; uint32_t bitmap_offset; uint32_t token_offset; uint8_t token_map_bmp[16] = {}; uint8_t token_map_tkn[16] = {}; const uint8_t* inp = src; const uint8_t* in_end = src + src_size; uint8_t* outp = dst; const uint8_t* out_end = dst + dst_size; const uint8_t* block_end; const uint8_t* bitmaps; const uint8_t* literals; const uint8_t* distances; unsigned n; unsigned m; unsigned o; const uint8_t* p; uint8_t tkn_split = 3; // TODO is dependent on flag ... uint8_t t; uint32_t rlecnt; uint16_t bitbuf; int nbits; uint32_t ntoken; uint32_t tmp_size; uint8_t bmp; uint8_t tkn; uint32_t dist; uint32_t bp; uint32_t dp; uint32_t lp; if (inp[0] != 'Z' || inp[1] != 'B' || inp[2] != 'M' || (inp[3] & 0xF0) != 0) return 0; flags = inp[3]; assert(flags == 9); if (flags != 9) { log_error("LZBITMAP: Flags != 0x09\n"); return 0; } inp += 4; while (true) { compressed_size = inp[0] | inp[1] << 8 | inp[2] << 16; uncompressed_size = inp[3] | inp[4] << 8 | inp[5] << 16; if (compressed_size == 6) { if (uncompressed_size != 0) log_error("LZBITMAP: Compressed size = 6, uncompressed size != 0???\n"); break; } if (compressed_size == uncompressed_size + 6) { if (outp + uncompressed_size > out_end || inp + compressed_size > in_end) { log_error("LZBITMAP: Buffer overrun.\n"); break; } memcpy(outp, inp + 6, uncompressed_size); outp += uncompressed_size; inp += compressed_size; continue; } distances_offset = inp[6] | inp[7] << 8 | inp[8] << 16; bitmap_offset = inp[9] | inp[10] << 8 | inp[11] << 16; token_offset = inp[12] | inp[13] << 8 | inp[14] << 16; literals = inp + 15; distances = inp + distances_offset; bitmaps = inp + bitmap_offset; p = inp + compressed_size - 0x11; for (n = 0; n < tkn_split; n++) { token_map_bmp[n] = 0; token_map_tkn[n] = n; } nbits = 0; bitbuf = 0; for (; n < 15; n++) { while (nbits < 10) { bitbuf |= *p << nbits; nbits += 8; p++; } token_map_bmp[n] = bitbuf & 0xFF; token_map_tkn[n] = bitbuf >> 8 & 3; bitbuf >>= 10; nbits -= 10; } ntoken = (uncompressed_size + 7) >> 3; tmp_size = compressed_size - token_offset - 0x11; for (n = 0; n < tmp_size; n++) { scratch[2 * n + 0x1000] = inp[token_offset + n] & 0xF; scratch[2 * n + 0x1001] = inp[token_offset + n] >> 4; } tmp_size *= 2; p = scratch + 0x1000; o = 0; for (n = 0; n < tmp_size; n++) { t = p[n]; if (t == 0xF) { t = p[n - 1]; rlecnt = 3; do { n++; rlecnt += p[n]; } while (p[n] == 0xF); for (m = 0; m < rlecnt; m++) scratch[o++] = t; } else { scratch[o++] = t; } } if (o != ntoken) log_debug("RLE size = %X, ntoken = %X\n", o, ntoken); o = 0; m = 0; dist = 8; dp = 0; bp = 0; lp = 0; block_end = outp + uncompressed_size; assert(block_end <= out_end); if (block_end > out_end) { log_error("LZBITMAP: Output buffer too small.\n"); block_end = out_end; } for (n = 0; n < ntoken; n++) { t = scratch[n]; if (t < tkn_split) bmp = bitmaps[bp++]; else bmp = token_map_bmp[t]; tkn = token_map_tkn[t]; if (tkn == 1) { dist = distances[dp++]; } else if (tkn == 2) { dist = distances[dp] | distances[dp + 1] << 8; dp += 2; } for (m = 0; m < 8 && outp < block_end; m++) { if (bmp & 1) *outp = literals[lp++]; else *outp = *(outp - dist); bmp >>= 1; outp++; } } if (lp != distances_offset - 15) log_error("lp = %06X (%06X)\n", lp, distances_offset - 15); if (dp != bitmap_offset - distances_offset) log_error("dp = %06X (%06X)\n", dp, bitmap_offset - distances_offset); if (bp != token_offset - bitmap_offset) log_error("bp = %06X (%06X)\n", bp, token_offset - bitmap_offset); inp += compressed_size; } return outp - dst; } int log2(uint32_t val) { int r = 0; if (val & 0xFFFF0000) { val >>= 16; r += 16; } if (val & 0xFF00) { val >>= 8; r += 8; } if (val & 0xF0) { val >>= 4; r += 4; } if (val & 0xC) { val >>= 2; r += 2; } if (val & 0x2) { val >>= 1; r += 1; } return r; } FILE *g_log = stderr; void log_debug(const char *msg, ...) { if (g_debug & Dbg_Cmpfs) { va_list va; va_start(va, msg); vfprintf(g_log, msg, va); va_end(va); } } void log_warn(const char *msg, ...) { if (g_debug & Dbg_Info) { va_list va; va_start(va, msg); vfprintf(g_log, msg, va); va_end(va); } } void log_error(const char *msg, ...) { if (g_debug & Dbg_Errors) { va_list va; va_start(va, msg); vfprintf(g_log, msg, va); va_end(va); } }