In this paper, we aim to bridge the gap between the energy efficiency of software and hardware video decoders by combining both DVFS and parallelism. For this purpose, we, first, propose an adaptive DVFS algorithm for energy efficient mono-core decoding of H.264 videos. The proposed solution uses metadata (normalized by MPEG) providing information about the upcoming workload. These metadata are processed within an adaptive filter to build dynamically an accurate complexity model used to calculate the minimal processor frequencies for decoding video frames while guaranteeing real time constraints. Then, we generalize the proposed DVFS to slice-based multi-threaded parallel video decoders on multi-core platforms. Our performance evaluations showed that the proposed algorithm for mono-core decoding is able to converge to an accurate complexity model (4 percent) in less than 1 second. Moreover, it is simple to implement, induces very low overhead and achieves up to 46 percent energy saving as compared to the ondemand Linux DVFS governor. On the other hand, joint use of parallelism and DVFS allows 720p software video decoding with only 17 percent more energy consumption as compared to a hardware video decoder.