payload: {"action":"created","issue":{"url":"https://api.github.com/repos/facebook/zstd/issues/1615","repository_url":"https://api.github.com/repos/facebook/zstd","labels_url":"https://api.github.com/repos/facebook/zstd/issues/1615/labels{/name}","comments_url":"https://api.github.com/repos/facebook/zstd/issues/1615/comments","events_url":"https://api.github.com/repos/facebook/zstd/issues/1615/events","html_url":"https://github.com/facebook/zstd/issues/1615","id":445049244,"node_id":"MDU6SXNzdWU0NDUwNDkyNDQ=","number":1615,"title":"Debugging compressed literals - single value huffWeights","user":{"login":"klauspost","id":5663952,"node_id":"MDQ6VXNlcjU2NjM5NTI=","avatar_url":"https://avatars3.githubusercontent.com/u/5663952?v=4","gravatar_id":"","url":"https://api.github.com/users/klauspost","html_url":"https://github.com/klauspost","followers_url":"https://api.github.com/users/klauspost/followers","following_url":"https://api.github.com/users/klauspost/following{/other_user}","gists_url":"https://api.github.com/users/klauspost/gists{/gist_id}","starred_url":"https://api.github.com/users/klauspost/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/klauspost/subscriptions","organizations_url":"https://api.github.com/users/klauspost/orgs","repos_url":"https://api.github.com/users/klauspost/repos","events_url":"https://api.github.com/users/klauspost/events{/privacy}","received_events_url":"https://api.github.com/users/klauspost/received_events","type":"User","site_admin":false},"labels":[{"id":169794530,"node_id":"MDU6TGFiZWwxNjk3OTQ1MzA=","url":"https://api.github.com/repos/facebook/zstd/labels/question","name":"question","color":"f4e8df","default":true}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2019-05-16T16:25:50Z","updated_at":"2019-05-16T17:09:06Z","closed_at":"2019-05-16T16:51:50Z","author_association":"NONE","body":"I am debugging an issue with the huffman compression and stumbled upon some weirdness centered around this line:\r\n\r\nhttps://github.com/facebook/zstd/blob/dev/lib/compress/huf_compress.c#L162\r\n\r\nFor my test I am only using the huffman encoder and to mimic my failure case I supplied it with this input:\r\n```Go\r\n\tfor i := 0; i < 255; i++ {\r\n\t\tbuf0 := make([]byte, BlockSizeMax)\r\n\t\tfor j := range buf0 {\r\n\t\t\tbuf0[j] = byte(int64(i) + (rng.Int63() & 3))\r\n\t\t}\r\n\t\tb, reUsed, err := Compress4X(buf0)\r\n\t}\r\n```\r\nThis works fine until `i` gets to `126`. My input basically looks like this: `[127 129 128 127 126 128 127...`\r\n\r\nThen the FSE encoder fails with a \"use RLE\" error, because the input is `[1,1,1,1....]`. In the reference code this means `HUF_compressWeights` returns 1 and therefore doesn't return. `huffLog` is 2.\r\n\r\nSince my `maxSymbolValue` is now `129` (biggest input) the line above fails and it refuses to compress my input. The comment suggests that this is \"should not happen\" and \"likely means source cannot be compressed\" - but that doesn't seem correct to me.\r\n\r\nAm I doing something wrong here, or is it just a very special case - and is it missing a way to represent RLE content?"},"comment":{"url":"https://api.github.com/repos/facebook/zstd/issues/comments/493152954","html_url":"https://github.com/facebook/zstd/issues/1615#issuecomment-493152954","issue_url":"https://api.github.com/repos/facebook/zstd/issues/1615","id":493152954,"node_id":"MDEyOklzc3VlQ29tbWVudDQ5MzE1Mjk1NA==","user":{"login":"Cyan4973","id":750081,"node_id":"MDQ6VXNlcjc1MDA4MQ==","avatar_url":"https://avatars0.githubusercontent.com/u/750081?v=4","gravatar_id":"","url":"https://api.github.com/users/Cyan4973","html_url":"https://github.com/Cyan4973","followers_url":"https://api.github.com/users/Cyan4973/followers","following_url":"https://api.github.com/users/Cyan4973/following{/other_user}","gists_url":"https://api.github.com/users/Cyan4973/gists{/gist_id}","starred_url":"https://api.github.com/users/Cyan4973/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Cyan4973/subscriptions","organizations_url":"https://api.github.com/users/Cyan4973/orgs","repos_url":"https://api.github.com/users/Cyan4973/repos","events_url":"https://api.github.com/users/Cyan4973/events{/privacy}","received_events_url":"https://api.github.com/users/Cyan4973/received_events","type":"User","site_admin":false},"created_at":"2019-05-16T17:09:06Z","updated_at":"2019-05-16T17:09:06Z","author_association":"CONTRIBUTOR","body":"On reaching line 162, the decision is to use the \"raw weight format\", which is limited to represent up to 129 symbols (hence values 0-128) only. Going above this upper bound makes the table encoding fails.\r\n\r\nIn general, this case is reached when compressing the huffman weights produces worse result than a direct \"raw\" format. This can happen when the alphabet size is very small. But as the alphabet size grows, it becomes less and less likely, and even downright impossible, if only because weights values are necessarily bounded between 0 and 11 (included), and therefore can be compressed to better than 4 bit per symbol. \r\n\r\nHere, this is different. Compressing the weights is possible, but it seems to produce a long sequence of 1, thus requiring the use of RLE mode.\r\nUnfortunately, FSE decompression does not handle \"natively\" the RLE case. This is supposed to be routed to a different code by the user layer, typically using `memset()`.\r\nSo FSE cannot compress that, so it defers to the \"raw\" mode, which fails, hence the error.\r\n\r\nIt seems this is a case which would require FSE decompression to handle RLE \"natively\". The problem is, any change now must remain compatible with the [RFC8478](https://tools.ietf.org/html/rfc8478). I don't remember the exact wording in the RFC for this part, but the main idea is : it's no longer possible to _add_ a decoder requirement at this stage.\r\n\r\nHaving all weights with a value `1` means that all symbols use the same nb of bits. This happens when data is not compressible, but it should not have reached this stage to begin with. That's in substance what the comment says.\r\nAnother possibility is that all symbols use the same nb of bits, but this nb is < 8, hence data is compressible. That's possible, but the sum of these weights must still be a power of 2, which means the nb of symbols present in the alphabet must 2, 4, 8, 16 etc. This includes 128 and 256, but 128 can be represented in the \"raw\" table mode, while 256 means it can't be compressed, so should not have reached this stage. Critically, no value between 129 and 255 is possible, since the sum is no longer a power of 2.\r\n\r\nNow, there is another subtlety : the last weight is not expressed. So we could have a situation where data is actually compressible, while weights to represent in the table are all `1`.\r\nBut there is another condition : it must still represent a perfect huffman distribution, so the sum of all `2^weight` must be a power of 2. \r\n\r\nThis leaves very little options to the table.\r\nBasically, the number of represented weights must be a power of 2, and the unrepresented last weight must be as important as the sum of all preceding weights.\r\nFor example : 16 x 1, implying a last 17th weight of 4.\r\n32x1, implying a last 33rd weight of 5. etc.\r\n\r\nThe only dangerous case is 128x1, implying a last 129th weight of 7.\r\n(256x1 + 8 is not possible, since alphabet size is necessarily <= 256).\r\nNow this is an alphabet of size 129.\r\nBut the thing is, we only represent 128 weights, so it still fits in the \"raw\" format, which can represent up to 128 weights (included).\r\n\r\nHence, if the analysis is correct, there should be no valid distribution of weights that can't be represented. If it nonetheless does, it might be because the distribution of weights is invalid, i.e. cannot be completed to represent a valid huffman tree. That also should should not happen, and if it does, it could mean that the code defining the huffman tree is buggy.\r\n"}}
other: {"actor":{"display_login":"Cyan4973"}}