diff --git a/doc/misc/tramp.texi b/doc/misc/tramp.texi
index 2eb5b45eb2..ade4d5cb2d 100644
--- a/doc/misc/tramp.texi
+++ b/doc/misc/tramp.texi
@@ -1960,16 +1960,31 @@ Remote programs
 @section How @value{tramp} finds and uses programs on the remote host
 
 @value{tramp} requires access to and rights to several commands on
-remote hosts: @command{ls}, @command{test}, @command{find} and
+remote hosts: at least @command{ls}, @command{test}, @command{find} and
 @command{cat}.
 
+For inline methods, at least one of the following should be available:
+
+@itemize @bullet
+@item @command{base64}
+@item @command{openssl}
+@item @command{mimencode}
+@item @command{mmencode}
+@item @command{recode}
+@item @command{perl} or @command{perl5} (if the  @command{MIME::Base64}
+module is available, it will be used)
+@item @command{od} and @command{busybox awk}
+@item @command{hexdump} and @command{busybox awk}
+@item @command{uuencode} and @command{uudecode}
+@end itemize
+
+If none of these are available, @value{tramp} will not work with inline methods,
+but other methods may still be used. If @command{gzip} is available, it is
+also used, in order to improve performance.
+
 Besides there are other required programs for @ref{Inline methods} and
 @ref{External methods} of connection.
 
-To improve performance and accuracy of remote file access,
-@value{tramp} uses @command{perl} (or @command{perl5}) and
-@command{grep} when available.
-
 @defopt tramp-remote-path
 @code{tramp-remote-path} specifies which remote directory paths
 @value{tramp} can search for @ref{Remote programs}.
diff --git a/lisp/net/tramp-sh.el b/lisp/net/tramp-sh.el
index 95fa61af98..fc2fb51b8a 100644
--- a/lisp/net/tramp-sh.el
+++ b/lisp/net/tramp-sh.el
@@ -850,8 +850,12 @@ tramp-perl-unpack
   "Perl program to use for decoding a file.
 Escape sequence %s is replaced with name of Perl binary.")
 
-(defconst tramp-awk-encode
-  "od -v -t x1 -A n | busybox awk '\\
+(defconst tramp-hexdump-awk-encode
+  "{ { awk '{}' </dev/null && BA=\"\"  ; } || \
+     { busybox awk '{}' </dev/null &&  BA=busybox ; } } && \
+   { { hexdump -v -e '16/1 \" %%02x\" \"\\n\"' < /dev/null && BH=\"\" ; } || \
+     { busybox hexdump -v -e '16/1 \" %%02x\" \"\\n\"' < /dev/null && BH=busybox ; } } && \
+$BH hexdump -v -e '16/1 \" %%02x\" \"\\n\"'| $BA awk '\\
 BEGIN {
   b64 = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/\"
   b16 = \"0123456789abcdef\"
@@ -881,11 +885,51 @@ tramp-awk-encode
   }
   printf tail
 }'"
-  "Awk program to use for encoding a file.
+  "Awk/hexdump program to use for encoding a file.
+This string is passed to `format', so percent characters need to be doubled.")
+
+(defconst tramp-od-awk-encode
+  "{ { awk '{}' </dev/null && BA=\"\"  ; } || \
+     { busybox awk '{}' </dev/null &&  BA=busybox  ; } } && \
+   { { od -v -t x1 -A n < /dev/null && BO=\"\" ; } || \
+     { busybox od -v -t x1 -A n < /dev/null && BO=busybox ; } } && \
+$BO od -v -t x1 -A n $BA awk '\\
+BEGIN {
+  b64 = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/\"
+  b16 = \"0123456789abcdef\"
+}
+{
+  for (c=1; c<=length($0); c++) {
+    d=index(b16, substr($0,c,1))
+    if (d--) {
+      for (b=1; b<=4; b++) {
+        o=o*2+int(d/8); d=(d*2)%%16
+        if (++obc==6) {
+          printf substr(b64,o+1,1)
+          if (++rc>75) { printf \"\\n\"; rc=0 }
+          obc=0; o=0
+        }
+      }
+    }
+  }
+}
+END {
+  if (obc) {
+    tail=(obc==2) ? \"==\\n\" : \"=\\n\"
+    while (obc++<6) { o=o*2 }
+    printf \"%%c\", substr(b64,o+1,1)
+  } else {
+    tail=\"\\n\"
+  }
+  printf tail
+}'"
+  "Awk/od program to use for encoding a file.
 This string is passed to `format', so percent characters need to be doubled.")
 
 (defconst tramp-awk-decode
-  "busybox awk '\\
+  "{ { awk '{}' </dev/null && B=\"\"  ; } || \
+     { busybox awk '{}' </dev/null &&  B=busybox  ; } } && \
+$B awk '\\
 BEGIN {
   b64 = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/\"
 }
@@ -910,11 +954,25 @@ tramp-awk-decode
   "Awk program to use for decoding a file.
 This string is passed to `format', so percent characters need to be doubled.")
 
-(defconst tramp-awk-coding-test
+
+(defconst tramp-hexdump-awk-coding-test
+  "test -c /dev/zero && \
+{ {          hexdump -v -e '16/1 \" %02x\" \"\\n\"' < /dev/null ; } || \
+  { busybox  hexdump -v -e '16/1 \" %02x\" \"\\n\"' < /dev/null ; }    } \
+&& \
+{ {         awk '{}' </dev/null ; } || \
+  { busybox awk '{}' </dev/null ; } } "
+  "Test command for checking `tramp-hexdump-awk-encode' and \
+`tramp-awk-decode'.")
+
+(defconst tramp-od-awk-coding-test
   "test -c /dev/zero && \
-od -v -t x1 -A n </dev/null && \
-busybox awk '{}' </dev/null"
-  "Test command for checking `tramp-awk-encode' and `tramp-awk-decode'.")
+{ {          od -v -t x1 -A n < /dev/null ; } || \
+  { busybox  od -v -t x1 -A n < /dev/null ; }    } \
+&& \
+{ {         awk '{}' </dev/null ; } || \
+  { busybox awk '{}' </dev/null ; } } "
+  "Test command for checking `tramp-od-awk-encode' and `tramp-awk-decode'.")
 
 (defconst tramp-vc-registered-read-file-names
   "echo \"(\"
@@ -3167,7 +3225,8 @@ tramp-sh-handle-file-local-copy
 
 	   ;; Oops, I don't know what to do.
 	   (t (tramp-error
-	       v 'file-error "Wrong method specification for `%s'" method)))
+	       v 'file-error  "Cannot find any way to encode data using `%s'"
+	       method)))
 
 	;; Error handling.
 	((error quit)
@@ -4370,8 +4429,10 @@ tramp-remote-coding-commands
     (b64 "recode data..base64" "recode base64..data")
     (b64 tramp-perl-encode-with-module tramp-perl-decode-with-module)
     (b64 tramp-perl-encode tramp-perl-decode)
-    ;; This is painful slow, so we put it on the end.
-    (b64 tramp-awk-encode tramp-awk-decode ,tramp-awk-coding-test)
+    ;; These is painfully slow, so we put it on the end.
+    (b64 tramp-od-awk-encode tramp-awk-decode ,tramp-od-awk-coding-test)
+    (b64 tramp-hexdump-awk-encode tramp-awk-decode
+	 ,tramp-hexdump-awk-coding-test)
     (uu  "uuencode xxx" "uudecode -o /dev/stdout" "test -c /dev/stdout")
     (uu  "uuencode xxx" "uudecode -o -")
     (uu  "uuencode xxx" "uudecode -p")