I've attached the second iteration of the patch. I've factored out a new function decompress_buf, and added two new (C only) instance variables input_buffer and input_buffer_size.

I've tested the patch by enabling Py_USING_MEMORY_DEBUGGER in Objects/obmalloc.c and compiling --with-pydebug --without-pymalloc. Output is:

$ valgrind --tool=memcheck --suppressions=Misc/valgrind-python.supp ./python -m test -R : -v test_lzma
==18635== Memcheck, a memory error detector
==18635== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==18635== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
==18635== Command: ./python -m test -R : -v test_lzma
==18635== 
== CPython 3.5.0a0 (default:a8f3ca72f703+, Apr 11 2014, 21:48:07) [GCC 4.8.2]
[....]
Ran 103 tests in 43.655s

OK
beginning 9 repetitions
123456789
[...]
OK
.
1 test OK.
==18635== 
==18635== HEAP SUMMARY:
==18635==     in use at exit: 2,328,705 bytes in 13,625 blocks
==18635==   total heap usage: 2,489,623 allocs, 2,475,998 frees, 91,305,463,593 bytes allocated
==18635== 
==18635== LEAK SUMMARY:
==18635==    definitely lost: 0 bytes in 0 blocks
==18635==    indirectly lost: 0 bytes in 0 blocks
==18635==      possibly lost: 963,533 bytes in 1,334 blocks
==18635==    still reachable: 1,365,172 bytes in 12,291 blocks
==18635==         suppressed: 0 bytes in 0 blocks
==18635== Rerun with --leak-check=full to see details of leaked memory
==18635== 
==18635== For counts of detected and suppressed errors, rerun with: -v
==18635== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)


When running the tests only once (no -R option), the number of possibly lost bytes is 544,068 in 1,131 blocks. When running without the patch, the number is 545,740 bytes in 1,134 blocks (for one iteration). I guess this means that Python is using interior pointers, so these blocks are not truly lost?